#include<iostream> #include<cstdio> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,K,dp[4005][4005],nxt1[4005][4005],nxt2[4005][4005]; vector<int>A[4005],B[4005]; void slv(){ n=read(),m=read(),K=read(); up(i,1,n)A[read()].p_b(i); up(i,1,m)B[read()].p_b(i); up(i,1,K)A[i].p_b(n+1),B[i].p_b(m+1); memset(dp,-1,sizeof(dp)); queue<pi>q;q.push(m_p(0,0)); dp[0][0]=0; up(i,1,K){ int id=0; up(j,0,n){ while(id<A[i].size()&&j>=A[i][id])id++; nxt1[j][i]=A[i][id]; } }up(i,1,K){ int id=0; up(j,0,m){ while(id<B[i].size()&&j>=B[i][id])id++; nxt2[j][i]=B[i][id]; } } while(!q.empty()){ int i=q.front().p1,j=q.front().p2;q.pop(); up(k,1,K){ int ni=nxt1[i][k]; int nj=nxt2[j][k]; if(i==n+1)ni=n+1; if(j==m+1)nj=m+1; if(dp[ni][nj]!=-1)continue; dp[ni][nj]=dp[i][j]+1; q.push(m_p(ni,nj)); if(ni==n+1&&nj==m+1){ printf("%d\n",dp[ni][nj]); return; } // if(dp[i][j]+1==dp[ni][nj])cout<<ni<<' '<<nj<<' '<<dp[ni][nj]<<' '<<i<<' '<<j<<'\n'; } } }int main(){ slv(); fclose(stdin); fclose(stdout); return 0; }