Description

Original source: CTSC 1997

Universities implement a credit system. Each course has a certain number of credits, and students can earn the corresponding credits by enrolling in and passing the course. A student's final credit total is the sum of the credits from all the courses they have taken.

Every student is required to select a specified number of courses. Some courses can be taken directly, while others require foundational knowledge and can only be taken after completing certain prerequisite courses. For example, Data Structures can only be taken after completing Advanced Programming Languages. We refer to Advanced Programming Languages as the prerequisite course for Data Structures. Each course has at most one direct prerequisite course. Two courses may share the same prerequisite course. For ease of reference, each course is assigned a unique course number, starting from $1, 2, 3, \cdots$.

Here is an example:

In the example above, Course No. $1$ is the prerequisite for Course No. $2$, meaning that to take Course No. $2$, Course No. $1$ must have been completed. Similarly, to take Course No. $3$, both Course No. $1$ and Course No. $2$ must have been completed.

Students cannot take all the courses offered by the university, so they must decide which courses to take upon enrollment. The total number of courses each student can select is predetermined. Your task is to find a course selection plan that maximizes the total credits earned while adhering to the prerequisite rules. Assume there are no scheduling conflicts between courses.

Input Format

The first line of input contains two positive integers $M$ and $N$, representing the number of available courses and the number of courses that can be selected, respectively.

The next $M$ lines each describe a course, with course numbers ranging from $1$ to $M$. Each line contains two numbers: the prerequisite course number (or $0$ if there is none) and the credits for that course.

Adjacent values are separated by spaces.

Output Format

Output a single line with the total credits earned from the selected courses.

Sample 1

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

13

Constraints & Notes

$1\le N \le M \le 100$, and the credits for each course do not exceed $20$.