#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fr first #define sc second #define mp make_pair #define ls p[now].son[0] #define rs p[now].son[1] #define lson pos<<1 #define rson pos<<1|1 const int MAXN=4010,Maxn=310,Mod=1004535809,base=131,mod=1011451423; int _,n,m,k,a[MAXN],b[MAXN]; int c[MAXN],ans; void dfs(int now,int A){ if(now>=ans)return; if(now>=max(n,m)+1)return; if(!A){ for(int i=1,j=1;i<=now;i++,j++){ while(j<=n&&a[j]!=c[i])j++; if(j>n){ A=1; break; } } } if(A){ for(int i=1,j=1;i<=now;i++,j++){ while(j<=m&&b[j]!=c[i])j++; if(j>m){ ans=now; return; } } } for(int i=1;i<=k;i++){ c[now+1]=i; dfs(now+1,A); } } inline void task1(){ ans=max(n,m)+1; dfs(0,0); printf("%d",ans); } int f[MAXN][MAXN],pa[MAXN][MAXN],pb[MAXN][MAXN]; inline void task2(){ for(int i=1;i<=k;i++)pa[n+1][i]=pa[n+2][i]=n+1; for(int i=n;i>=0;i--){ for(int j=1;j<=k;j++){ pa[i][j]=pa[i+1][j]; } pa[i][a[i]]=i; } for(int i=1;i<=k;i++)pb[m+1][i]=pb[m+2][i]=m+1; for(int i=m;i>=0;i--){ for(int j=1;j<=k;j++){ pb[i][j]=pb[i+1][j]; } pb[i][b[i]]=i; } for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)f[i][j]=1e9; f[0][0]=0; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ for(int o=1;o<=k;o++){ // cout<<i<<" "<<j<<" "<<o<<" "<<f[i][j]<<" "<<pa[i+1][o]<<" "<<pb[j+1][o]<<endl; f[pa[i+1][o]][pb[j+1][o]]=min(f[pa[i+1][o]][pb[j+1][o]],f[i][j]+1); } } } printf("%d",f[n+1][m+1]); } /* int qry(int xl,int xr,int yl,int yr){ int rt=1e9; for(int i=xl;i<=xr;i++){ for(int j=yl;j<=yr;j++){ rt=min(rt,f[i][j]); } } return rt; } inline void task3(){ for(int i=1;i<=k;i++)pa[1][i]=pa[0][i]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ pa[i][j]=pa[i-1][j]; } pa[i][a[i]]=i; } for(int i=1;i<=k;i++)pb[1][i]=pb[0][i]=0; for(int i=1;i<=m;i++){ for(int j=1;j<=k;j++){ pb[i][j]=pb[i-1][j]; } pb[i][b[i]]=i; } for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)f[i][j]=1e9; f[0][0]=0; for(int i=1;i<=n+1;i++){ for(int j=1;j<=m+1;j++){ if(i!=n+1&&j!=m+1&&a[i]!=b[j])continue; if(i==n+1)a[i]=b[j]; if(j==m+1)b[j]=a[i]; if(i==n+1&&j==m+1){ for(int o=1;o<=k;o++){ f[i][j]=min(f[i][j],qry(pa[i-1][o],i-1,pb[j-1][o],j-1)+1); } } else { int o=a[i]; f[i][j]=min(f[i][j],qry(pa[i-1][o],i-1,pb[j-1][o],j-1)+1); } } } printf("%lld",f[n+1][m+1]); }*/ inline void slv(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=m;i++){ scanf("%d",&b[i]); } if(n<=18&&m<=18&&k==2)task1(); else task2(); } signed main(){ // scanf("%lld",&_);while(_--) slv(); return 0; }