题目描述

大学里每个学生需要修满一定的学分才能毕业。课程之间存在先修关系：有些课程必须在另一些课程之前学习，例如高等数学通常需要在其他课程之前修完。

现在共有 $N$ 门课程，每门课有若干学分，分别记作 $s_1, s_2, \cdots, s_N$。每门课有至多一门直接先修课（若课程 $a$ 是课程 $b$ 的先修课，即只有学完了课程 $a$ 才能学习课程 $b$）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

题目保证课程安排无冲突，即不会出现循环先修关系。

输入格式

第一行有两个整数 $N$，$M$，用空格隔开 $(1 \leq N \leq 300, 1 \leq M \leq 300)$。

接下来的 $N$ 行，第 $i+1$ 行包含两个整数 $k_i$ 和 $s_i$，$k_i$ 表示第 $i$ 门课的直接先修课编号，$s_i$ 表示第 $i$ 门课的学分。若 $k_i=0$ 表示没有直接先修课 $(0 \leq k_i \leq N, 1 \leq s_i \leq 20)$。

数据保证至少存在一个 $k_i=0$，即至少一门课无先修课。

输出格式

只有一行，选 $M$ 门课程的最大学分。

样例

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

13