P1273

#include <bits/stdc++.h>
using namespace std;
const int N=3010;
int n,m,s;
vector <int> tree[N];
int w[N][N];
int p[N];
int dp[N][N];
int dfs(int u){
	if(u>=s+1){
		dp[u][1]=p[u];
		dp[u][0]=0;
		return 1;
	} 
	int tmp=0;
	dp[u][0]=0;
	for(int i=0;i<tree[u].size();i++){
		int v=tree[u][i];
		int t=dfs(v);
		tmp+=t;
		for(int j=tmp;j>=0;j--){
			for(int k=1;k<=min(j,t);k++){
				dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-w[u][v]);
			}
		}
	}
	return tmp;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    s=n-m;
    for(int i=1;i<=s;i++){
    	int l;
    	cin>>l;
    	for(int j=1;j<=l;j++){
    		int s1,s2;
    		cin>>s1>>s2;
    		w[i][s1]=s2;
    		tree[i].push_back(s1);
		}
	}
	for(int i=s+1;i<=n;i++){
		cin>>p[i];
	}
 	memset(dp,sizeof(dp),-0x3f);
	dfs(1);
	for(int i=m;i>=0;i--){
		if(dp[1][i]>=0){
			cout<<i<<'\n';
			break;
		}
	}
	return 0;
}