/* Subtask 1 - 5를 해결하는 코드 */
#include <vector>
#include <malloc.h>
#include <algorithm>
using namespace std;
namespace sttic { int N, M, F, K; };
using namespace sttic;
const int N_ = 5005;
const int INF = 987654321;
int Table[3005][10005];
vector< vector<int> > Gph;
struct Intv {
int l, r, ln, rn;
Intv(): l(0), r(0), ln(0), rn(0) { }
Intv(int l, int r): l(l), r(r), ln(0), rn(0) { }
bool operator< (const Intv &t) const {
if(l == INF) return false;
if(t.l == INF) return true;
return r != t.r ? r < t.r : l > t.l;
}
} *D;
int file;
void Renumber( int node ){
int i;
if(node >= M){ // leaf node
D[node].l = D[node].r = ++file;
}else{
D[node].l = INF;
D[node].r = -INF;
for(int i = 0; i < Gph[node].size(); i++){
int g = Gph[node][i];
Renumber(g);
D[node].l = min(D[node].l, D[g].l);
D[node].r = max(D[node].r, D[g].r);
}
}
}
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;
sttic::F = N + M;
Gph.resize(M);
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 );
D = (Intv*) calloc( F, sizeof(Intv) );
Renumber (0);
sort(D, D + M);
while(D[M - 1].l == INF && M > 0) --M;
vector<int> X;
X.push_back(0);
for(i = 0; i < M; i++) X.push_back( D[i].r );
sort( X.begin(), X.end() );
X.resize( distance( X.begin(), unique( X.begin(), X.end() ) ) );
for(i = 0; i < M; i++){
D[i].ln = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].l - 1) );
D[i].rn = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].r ) );
//printf("%3d : [%3d, %3d] [%3d, %3d]\n", i, D[i].l - 1, D[i].r, D[i].ln, D[i].rn );
}
for(i = 0; i < X.size(); i++){
for(j = 1; j <= K; j++) Table[i][j] = INF;
}
for(j = 1; j <= D[0].r; j++) Table[0][j] = j;
for(i = 0; i < M; i++){
Intv &d = D[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.rn][j];
t = min(t, Table[d.rn - 1][j]);
if(j >= len) t = min(t, Table[d.ln][j - len] + 1);
}
if(i + 1 < M && d.rn != D[i + 1].rn){
for(j = d.r + 1; j <= D[i + 1].r && j <= K; j++)
Table[d.rn][j] = min(Table[d.rn][j], Table[d.rn][j - 1] + 1);
}
}
for(i = 0; i <= K; i++){
int val = Table[D[M - 1].rn][i] + (K - i);
if(val < ret) ret = val;
}
return ret;
}
