#include <bits/stdc++.h>
using namespace std;

#ifndef ONLINE_JUDGE
#include "algo/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
const int INF = 1e9;
void solve() {
	int g;
	cin >> g;
	vector<string> s(g);
	for (auto &x : s) {
		cin >> x;
	}

	vector<vector<int>> dis(g, vector<int>(g, 0));

	for (int i = 0; i < g; i++) {
		for (int j = 0; j < g; j++) {
			int c = 0;
			for (int k = 0; k < s[i].size(); k++) {
				if (s[i][k] != s[j][k]) {
					c++;
				}
			}
			dis[i][j] = c;
		}
	}

	int t;
	cin >> t;
	if (t == 0) {
		cout << "\n";
	}
	while (t--) {
		int n, m;
		cin >> n >> m;
		if (n == 0) {
			cout << 0 << '\n';
			return;
		}
		vector<vector<int>> v(n);
		for (int i = 0, x; i + 1 < n; i++) {
			cin >> x;
			x--;
			v[i + 1].push_back(x);
			v[x].push_back(i + 1);
		}

		vector<vector<int>> dp(n, vector<int>(g, INF));
		// dp[node][id] -> assign s[id] to node and find the min weight in the subtree of node.

		vector<int> giv(n, 0);
		for (int j = 0, l, id; j < m; j++) {
			cin >> l >> id;
			id--; l--;

			giv[l] = 1;
			dp[l][id] = 0;
		}

		function<void(int, int)> dfs = [&](int node, int p) {
			for (auto ch : v[node]) {
				if (ch ^ p) {
					dfs(ch, node);
				}
			}
			if (!giv[node]) {
				for (int i = 0; i < g; i++) {
					int s = 0;
					for (auto ch : v[node]) {
						if (ch ^ p) {
							int mn = INF;
							for (int j = 0; j < g; j++) {
								mn = min(mn, dp[ch][j] + dis[i][j]);
							}
							s += mn;
						}
					}
					dp[node][i] = s;
				}
			}
		};

		dfs(0, -1);

		cout << *min_element(dp[0].begin(), dp[0].end()) << '\n';
	}
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int t = 1;
	//cin >> t;

	while (t--) {
		solve();
	}

	// cerr << "Time elapsed: " << ((long double)clock() / CLOCKS_PER_SEC) << " s.\n";
}

#include <bits/stdc++.h>
using namespace std;
#define siddhantnema ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define inparr(arr, N) for (ll i = 0; i < N; i++) { cin >> arr[i]; }
#define forn(_i, N) for (ll _i = 0; _i < N; _i++)
#define trc(x) cout << #x << " -> " << x << '\n';
#define len(x) (int)x.size()

ll arr[(int)1e6 + 69];
ll DP[(int)1e6 + 69];

ll rec(ll pos, ll N, vector<ll> &diff, map<ll, ll> &ok)
{
    if(DP[pos] != -1)
        return DP[pos];
    if(pos == N)
        return DP[pos] = 0;
    
    ll res = max(1LL, rec(pos + 1, N, diff, ok));
    for(auto &i: diff)
    {
        if(not ok.contains(arr[pos] + i))
            continue;
        
        if(ok[arr[pos] + i] > pos)
            res = max(res, 1 + rec(ok[arr[pos] + i], N, diff, ok));
    }

    return DP[pos] = res;
}

void solve()
{
    ll N, K;
    cin >> N >> K;
    inparr(arr, N);

    vector<ll> diff(K);
    inparr(diff, K);

    map<ll, ll> ok;
    forn(i, N)
        ok[arr[i]] = i;
    
    forn(i, N + 1)
        DP[i] = -1;

    cout << rec(0LL, N, diff, ok) << '\n';
}

signed main() 
{ 
    siddhantnema
    #ifndef ONLINE_JUDGE
        freopen("output.txt", "w", stdout);
        freopen("input.txt", "r", stdin);
    #endif

    ll t = 1;
    // cin >> t;
    forn(_, t) 
    {
        #ifndef ONLINE_JUDGE
        cout << "Test Case #" << _ + 1 << '\n';
        #endif
        solve();
    }
}

#include<bits/stdc++.h>
//#include <sys/resource.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
 
#define all(x) x.begin(), x.end()
#define nl cout<<"\n"
#define ar  array
#define PRECISION 9
#define fast_IO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define clock() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define size(x) (int)x.size()
#define pb push_back
#define fr(i,j,k) for(int i=j;i<k;i++)
#define rf(i,j,k) for(int i=k-1;i>j;i--)

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// const ll p = uniform_int_distribution<ll>(0, mod - 1)(rng);

//#define STACK_INCREASE

void solve(){
    int n,k;
    cin>>n>>k;
    vi adj[n];
    vl val(n);
    fr(i,0,n){
        int u,c;
        cin>>u>>c;
        --u;
        if(i==0) val[0]=c;
        else{
            val[i]=c;
            adj[u].pb(i);
        }
    }
    ll ans=0,cur=0;
    set<ll>s1,s2;
    auto add=[&](ll x){
        s1.insert(x);
        cur+=x;
        while(size(s1)>k) {
            auto it=*s1.begin(); 
            s1.erase(it);
            cur-=it;
            s2.insert(it);
        }
    };
    auto rem=[&](ll x){
        if(s2.find(x)!=s2.end()) {
            s2.erase(x);
        }
        else {
            cur-=x;
            s1.erase(x);
            while(size(s1)<k && size(s2)>0) {
                auto it=*s2.rbegin();
                cur+=it;
                s2.erase(it);
                s1.insert(it);
            }
        }
    };
    function<void(int)>dfs=[&](int u){
        add(val[u]);
        ans=max(ans,cur);
        for(auto v:adj[u]){
            dfs(v);
        }
        rem(val[u]);
        ans=max(ans,cur);
    };
    dfs(0);
    cout<<ans;
}


int main(){
    if (0) cout<<fixed<<setprecision(PRECISION);
    fast_IO;
    #ifdef STACK_INCREASE
    rlimit rlim;
    if (getrlimit(RLIMIT_STACK, &rlim)) return 1;
    rlim.rlim_cur = 1024*1024*1024;
    if (setrlimit(RLIMIT_STACK, &rlim)) return 2;
    #endif
    int T=1;
    // cin>>T;
    while(T--){
        solve();
        clock();
    }
    return 0;
}