subject

The school implements the credit system.

Each compulsory course has fixed credits, and must also obtain corresponding elective course credits.

The school offers N elective courses, and the number of optional courses M for each student is given.

Students who take this M course and pass the examination can obtain corresponding credits.

Among the elective courses, some courses can be taken directly, and some courses need some basic knowledge. They can only be taken on the basis of other courses.

For example, "Windows programming" can only be selected after taking "Fundamentals of Windows operation".

We call "Fundamentals of Windows operation" a prerequisite course of "Windows programming".

There is only one direct prerequisite for each course at most.

The two courses may have the same prerequisites.

Your task is to determine a course selection scheme for yourself, so that you can get the most credits, and you must meet the prerequisites.

It is assumed that there is no time conflict between courses.

Input format
The first line of the input file includes two integers N and M (separated by a space in the middle), where 1 ≤ N ≤ 300 and 1 ≤ M ≤ N.

The next N lines represent a course, and the course numbers are 1, 2,..., n.

Each line has two numbers (separated by a space). The first number is the class number of the prerequisite course of this course (if there is no prerequisite course, this item is 0), and the second number is the credits of this course.

Credits are positive integers up to 10.

Output format
Output an integer representing the total number of credits.

Input sample:
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
Output example:
13

thinking

This problem is very similar to the boss's ball, but it's very different. First, we don't have only one tree in this problem. All dependencies may be given in the form of forest. Second, how to deal with the dependencies between these classes. So for the first question, we can use a common idea in graph theory to build a super source point, and then just need to find the dp value of point 0. For the second point, we can regard the N trees hanging under one point as n groups of backpacks. The volume of items in each group of backpacks is 1 to m-1. Then we make a group backpack, but we should pay attention to subtracting 1 from the total volume when making a backpack, and keep the position of the father to ensure the dependency.

code implementation

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=0;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005 
#define fi first 
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') {
        if(ch=='-') f = -1;
        ch=getchar();
    } 
    while('0'<=ch&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }   return x*f;
}

const int maxn=310;
int  n,m;
vector <int > v[maxn];
int w[maxn];
int f[maxn][maxn];   //f[root][m]

void dfs (int u) {
    rev (i,0,v[u].size ()) {
        int son=v[u][i];
        dfs (son);
        
        per (j,m-1,0) {
            rep (k,1,j) {
                f[u][j]=max (f[u][j],f[u][j-k]+f[son][k]);
            }
        }
    }
    per (i,m,1) {
        f[u][i]=f[u][i-1]+w[u];
    }
    f[u][0]=0;
}

int main () {
    cin>>n>>m;
    rep (i,1,n) {
       int a;
       cin>>a>>w[i];
       v[a].pb (i);
    }
    m++;
    dfs (0);

    cout<<f[0][m]<<endl;

    return 0;
}