#include<algorithm>
#include<string.h>
using namespace std;
int Dp[3030][10010];
int R[3030],L[3030],tot[3030];
int st[3030],en[6060];
short next[6060];
bool check[3030];
int ord[3030],co;
int now,sum;
void dfs(int x)
{
check[x]=1;
L[x]=now;
for(int i=st[x];i;i=next[i]){
if(!check[en[i]]){dfs(en[i]);tot[x]+=tot[en[i]];}
}
ord[++co]=now=x;
}
void addedge(int s,int d,int c)
{
next[c]=st[s];
st[s]=c;
en[c]=d;
}
int DeletePlan( int M, int N, int K, int *A, int *B){
int i;
for(i=0;i<M;i++){R[A[i]]++;tot[A[i]]++;}
for(i=1;i<N;i++){
addedge(i,B[i],2*i);
addedge(B[i],i,2*i+1);
}
dfs(0);
memset(Dp,1,sizeof(Dp));
Dp[0][0]=0;
for(i=1;i<=N;i++){
int x=ord[i],j;
for(j=0;j<=sum;j++)Dp[x][j]=Dp[ord[i-1]][j];
for(j=sum+1;j<=sum+R[x];j++)Dp[x][j]=Dp[x][j-1]+1;
for(j=sum+R[x];j>=tot[x];j--){
Dp[x][j]=min(Dp[x][j],Dp[L[x]][j-tot[x]]+1);
}
sum+=R[x];
}
return Dp[0][K];
}
