Description

At a university, to reach a certain number of credits, each student must choose some courses from many options. Among the courses, some must be taken before others; for example, Advanced Mathematics is always taken before other courses. Now there are $N$ courses, each with some credits, denoted as $s_1,s_2,\cdots,s_N$. Each course has one direct prerequisite or none (if course $a$ is a prerequisite of course $b$, then one can study course $b$ only after finishing course $a$). A student needs to choose $M$ courses from these courses. What is the maximum total number of credits he can obtain?

The problem guarantees that the course arrangement has no conflicts. (That is, there is no situation where $a$ is a prerequisite of $b$ while $b$ is also a prerequisite of $a$.)

Input Format

The first line contains two integers $N$, $M$ separated by a space $(1 \leq N \leq 300$ , $1 \leq M \leq 300)$.

The next $N$ lines: the $(i+1)$-th line contains two integers $k_i$ and $s_i$, where $k_i$ is the direct prerequisite of course $i$, and $s_i$ is the credits of course $i$. If $k_i=0$, it means there is no direct prerequisite $(0 \leq {k_i} \leq N$,$1 \leq {s_i} \leq 20)$.

The testdata guarantees that there exists at least one $k_i=0$, i.e., there is at least one course without a prerequisite.

Output Format

Output a single line containing the maximum total credits when choosing $M$ courses.

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

13

Hint

Translated by ChatGPT 5