#include <vector>
#include <algorithm>
using namespace std;
const int SZ = 3005;
const int INF = 987654321;
namespace sttic {
int N, M, K;
};
struct Intv {
int l, r;
Intv(): l(0), r(0) { }
Intv(int l, int r): l(l), r(r) { }
};
using namespace sttic;
vector<int> Gph[SZ];
vector<Intv> I;
int Table[SZ][SZ];
int file;
void getInterval (int node){
int i;
if(node >= M) {
++file;
I.push_back( Intv(file, file) );
}else {
int st = file + 1;
for(i = 0; i < Gph[node].size(); i++){
int g = Gph[node][i];
getInterval(g);
}
if(st <= file) I.push_back( Intv(st, file) );
}
}
int DeletePlan( int N, int M, int K, int *A, int *B) {
int i, j;
sttic::N = N; sttic::M = M; sttic::K = K;
for(i = 0; i < N; i++) Gph[ A[i] ].push_back(i + M);
for(i = 1; i < M; i++) Gph[ B[i] ].push_back(i);
getInterval(0);
for(i = 0; i <= N; i++){
for(j = 1; j <= K; j++) Table[i][j] = INF;
}
/*
for(i = 0; i < I.size(); i++){
Intv &d = I[i]; int len = d.r - d.l + 1;
for(j = 1; j <= K && j <= d.r; j++){
int &t = Table[d.r][j];
t = min(t, Table[d.r - 1][j]);
if(j >= len) t = min(t, Table[d.l - 1][j - len] + 1);
}
}*/
for(j = 1; j <= K; j++) {
for(i = 0; i < I.size(); i++) {
Intv &d = I[i]; int len = d.r - d.l + 1;
int &t = Table[d.r][j];
t = min(t, Table[d.l - 1][j]);
if(j >= len) t = min(t, Table[d.l - 1][j - len] + 1);
}
}
return Table[N][K];
}
