seereja and two sequences

/* seereja and two sequences */

/* In thgis problem we will use dynamic programming: dpi, j — minimal pozition of deleted element in second array, such that we have made first operation j times and have deleted not more then i elements from first array.

Lets decided how to calculate transfers. Standing in pozition dpi, j we can change nothing and go to pozition dpi + 1, j, by other words make transfer dpi + 1, j:  = min(dpi + 1, j, dpi, j). What happens when we make first operation with fixed prefix(by i-th element) in first array? We should find element in second array with number greater dpi, j and value equal to ai, lets its pozition is t, so we need to make transfer dpi + 1, j + 1:  = min(dpi + 1, j + 1, t).

How to find required element quickly: lets just do vector of pozition in second array for all different elements that contains in second array. Then we can simply use binary search.  */

int arr[MAX],brr[MAX];vi v[MAX];int id[MAX];int I[MAX],pos[MAX];

int dp[350][MAX];


int main()
{
    booster()
    //read("input.txt");

    int n,m,s,e;
    cin>>n>>m>>s>>e;

    for(int i = 1;i<=n;i++)cin>>arr[i];
    for(int i = 1;i<=m;i++){
        cin>>brr[i];
        v[brr[i]].pb(i);
    }

    int maxn = s/e;
    int ans = 0;

    dp[0][0] = 0;
    for(int i = 1;i<=maxn;i++){
        dp[i][0] = inf / 10;
        for(int j = 1;j<=n;j++){
            auto x = upper_bound(all(v[arr[j]]),dp[i-1][j-1]) ;
            if(x==v[arr[j]].end()){
                dp[i][j] = inf / 10;
            }
            else dp[i][j] = *x;
            dp[i][j] = min(dp[i][j-1],dp[i][j]);
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = maxn;j>=1;j--){
            if(i + dp[j][i] + (j*e)<=s)ans = max(ans,j);
        }
    }
    cout<<ans;




    return 0;
}