Problem: A boy PCK had N straight iron bars, which were serially indexed. Unfortunately, the first M bars (0 ≤ M ≤ N) among them were bent during transportation. They all suffered a perpendicular bend at one point.

He is planning to make a cube using a set of bars selected using the following rules: X bars from bent ones, Y bars from straight ones, where 2X + Y = 12. Any two bars can be jointed only at the apexes of the cube. He wants to count how many types of rectangular parallelepipeds (hereafter RP) he can make using these bars.

Make a program to count out types (different shapes) of RPs that PCK can make using the following information: the number of bars and length of each one, position of the bend, and the number of bars to be used to construct an RP. Note that any two RPs similar in shape are considered identical: namely if the length of three defining sides of two RPs coincide if arranged in increasing/decreasing order (e.g., three sides of RP i and j are A_i, B_i, C_i, and A_j, B_j and C_j in increasing order, then the relations A_i = A_j, B_i = B_j, and C_i = C_j hold. Note also that the bars are sufficiently thin to allow you to consider them as idealized lines.



Input

The input is given in the following format.


N M X Y
a_1
a_2
:
a_N
b_1
b_2
:
b_M


The first line provides the total number of iron bars and bent bars, and those straight and bent bars used to construct an RP: N (6 ≤ N ≤ 6000), M (0 ≤ M ≤ N), X (0 ≤ X ≤ 6), and Y (0 ≤ Y ≤ 12). The following relations always hold for them: 2X+Y=12, X+Y ≤ N, X ≤ M. Each of the subsequent N lines provides the length of the i-th bar a_i (1 ≤ a_i ≤ 6000) in integers. Furthermore, each of the subsequent M lines provides the location at which the i-th bent bar suffered a perpendicular bend b_i (1 ≤ b_i ≤ 3000) in centimeters from one end of the bar (note: 1 ≤ a_i-b_i ≤ 3000).

Output

Output the number of constructible rectangular parallelepipeds.

Example

Input

18 8 3 6
4
3
3
3
3
2
2
2
1
1
1
1
1
2
2
3
3
3
1
1
1
1
1
1
1
1


Output

3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,X,Y;

int A[6000],B[6000][6000];

vint G[6000];

int sum[6666];

int memo[5][5][5][5][5][5];

int calc(int a,int b,int c,int ab,int bc,int ca){
    chmin(a,4);chmin(b,4);chmin(c,4);chmin(ab,4);chmin(bc,4);chmin(ca,4);

    int &ret=memo[a][b][c][ab][bc][ca];
    if(ret!=-1)return ret;

    ret=0;
    rep(i,ab+1)rep(j,bc+1)rep(k,ca+1){
        if(i+j+k!=X)continue;
        if(4-i-k<=a&&4-i-j<=b&&4-j-k<=c&&i+k<=4&&i+j<=4&&j+k<=4)ret=1;
    }
    return ret;
}

signed main(){
    memset(memo,-1,sizeof(memo));

    cin>>N>>M>>X>>Y;
    vint a(N);
    rep(i,N)cin>>a[i];
    rep(i,M){
        int b;cin>>b;
        int c=a[i]-b;
        b--;c--;
        B[b][c]++;
        if(b!=c){
            if(B[c][b]==0)G[min(b,c)].pb(max(b,c));
            B[c][b]++;
        }
    }

    for(int i=M;i<N;i++)A[a[i]-1]++;

    rep(i,6000){
        sum[i]+=A[i]>=4;
        sum[i+1]=sum[i];
    }

    int ans=0;
    rep(i,6000){
       if(B[i][i]>=X&&A[i]>=Y)ans++;
    }

    rep(i,6000)rep(j,6000){
        if(i==j)continue;
        bool ok=false;
        for(int k=0;k<=4&&k<=B[i][i]&&k<=X;k++){
            int l=X-k;
            if(l>4||k*2+l>8||l>B[i][j])continue;

            int x=8-2*k-l;
            int y=4-l;
            if(x<=A[i]&&y<=A[j])ok=true;
        }
        ans+=ok;
    }



    rep(i,6000){
        for(int j=i+1;j<6000;j++){
            int tmp=sum[6000]-sum[j];



            for(auto k:G[i]){
                if(k<=j)continue;

                ans+=calc(A[i],A[j],A[k],B[i][j],B[j][k],B[k][i]);
                if(A[k]>=4)tmp--;
            }
            for(auto k:G[j]){
                if(B[i][k])continue;
                ans+=calc(A[i],A[j],A[k],B[i][j],B[j][k],B[k][i]);
                if(A[k]>=4)tmp--;
            }

            if(B[i][j]>=X&&X<=4&&4-X<=A[i]&&4-X<=A[j])ans+=tmp;
        }
    }

    cout<<ans<<endl;
    return 0;
}