#include <bits/stdc++.h> using namespace std; //#define int long long #define endl "\n" #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define pii pair<int,int> #define p1(x) (x).first #define p2(x) (x).second int n,m,k; int a[4010],b[4010]; int nta[4010][4010],ntb[4010][4010],f[4010][4010]; inline void chkmn(int &x,int y){x=min(x,y);} signed main() { // freopen("subsequence.in","r",stdin); // freopen("subsequence.out","w",stdout); ios::sync_with_stdio(0); cin>>n>>m>>k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=m;i++)cin>>b[i]; for(int i=0;i<=k;i++)nta[n+1][i]=nta[n+2][i]=n+1,ntb[m+1][i]=ntb[m+2][i]=m+1; for(int i=n;i>=0;i--)memcpy(nta[i],nta[i+1],sizeof(nta[i])),nta[i][a[i]]=i; for(int i=m;i>=0;i--)memcpy(ntb[i],ntb[i+1],sizeof(ntb[i])),ntb[i][b[i]]=i; memset(f,0x3f,sizeof(f)); f[0][0]=0; for(int i=0;i<=n;i++){ int MN=1e4; for(int j=m+1;j>=0;j--){ MN=min(MN,f[i][j]); if(j!=m+1&&j!=0)chkmn(f[nta[i+1][b[j]]][ntb[j+1][b[j]]],MN+1); else for(int p=1;p<=k;p++)chkmn(f[nta[i+1][p]][ntb[j+1][p]],MN+1); } } for(int i=1;i<=m;i++)for(int j=1;j<=k;j++)chkmn(f[n+1][ntb[i+1][j]],f[n+1][i]+1); cout<<f[n+1][m+1]<<endl; cout.flush(); return 0; } /* 3 2 2 1 2 1 2 2 */