#include <vector>
#include <algorithm>
using namespace std;
const int N_ = 10005, M_ = 3005;
const int INF = 987654321;
namespace sttic {
int N, M, K;
};
struct Intv {
int l, r, lp, rp;
Intv(): l(0), r(0), lp(-1), rp(-1) { }
Intv(int l, int r): l(l), r(r), lp(-1), rp(-1) { }
Intv(int l, int lp, int r, int rp): l(l), r(r), lp(lp), rp(rp) { }
};
using namespace sttic;
vector<int> Gph[M_];
vector<Intv> I;
int Table[M_][N_];
int file;
void getInterval (int node){
int i;
if(node >= M) {
++file;
}else {
int st = file + 1;
for(i = 0; i < Gph[node].size(); i++) getInterval(Gph[node][i]);
if(st <= file) I.push_back( Intv(st, file) );
}
}
int DeletePlan( int N, int M, int K, int *A, int *B) {
int i, j, ret = K;
sttic::N = N; sttic::M = M; sttic::K = K;
for(i = 1; i < M; i++) Gph[ B[i] ].push_back(i);
for(i = 0; i < N; i++) Gph[ A[i] ].push_back(i + M);
getInterval(0);
vector<int> X;
X.push_back(0);
for(i = 0; i < I.size(); i++) X.push_back( I[i].r );
sort( X.begin(), X.end() );
X.resize( distance( X.begin(), unique( X.begin(), X.end() ) ) );
for(i = 0; i < I.size(); i++){
I[i].lp = lower_bound( X.begin(), X.end(), I[i].l - 1) - X.begin();
I[i].rp = lower_bound( X.begin(), X.end(), I[i].r ) - X.begin();
}
for(i = 0; i < X.size(); i++){
for(j = 1; j <= K; j++) Table[i][j] = INF;
}
for(j = 1; j <= I[0].r; j++) Table[0][j] = j;
for(i = 0; i < I.size(); i++){
Intv &d = I[i]; int len = d.r - d.l + 1;
if(d.l == INF) continue;
for(j = 1; j <= K && j <= d.r; j++){
int &t = Table[d.rp][j];
t = min(t, Table[d.rp - 1][j]);
if(j >= len) t = min(t, Table[d.lp][j - len] + 1);
}
if(i + 1 < I.size() && d.rp != I[i + 1].rp){
for(j = d.r + 1; j <= I[i + 1].r && j <= K; j++)
Table[d.rp][j] = min(Table[d.rp][j], Table[d.rp][j - 1] + 1);
}
}
for(i = 0; i <= K; i++){
int val = Table[I.back().rp][i] + (K - i);
if(val < ret) ret = val;
}
return ret;
}
