Problem: You have 4 bags A, B, C and D each of which includes N coins (there are totally 4N coins). Values of the coins in each bag are ai, bi, ci and di respectively.

Find the number of combinations that result when you choose one coin from each bag (totally 4 coins) in such a way that the total value of the coins is V. You should distinguish the coins in a bag.

Constraints

* 1 ≤ N ≤ 1000
* 1 ≤ ai, bi, ci, di ≤ 1016
* 1 ≤ V ≤ 1016
* All input values are given in integers

Input

The input is given in the following format.


N V
a1 a2 ... aN
b1 b2 ... bN
c1 c2 ... cN
d1 d2 ... dN


Output

Print the number of combinations in a line.

Examples

Input

3 14
3 1 2
4 8 2
1 2 3
7 3 2


Output

9


Input

5 4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1


Output

625

Solution (in CPP):

Solution:


#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}

map<int,int> f(map<int,int> a,map<int,int> b){
  map<int,int> res;
  for(P ma:a){
    for(P mb:b){
      
      res[ma.F+mb.F]+=ma.S*mb.S;
    }
  }

  return res;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n,v;
  cin>>n>>v;
  map<int,int> mpa,mpb,mpc,mpd;
  rep(i,n){
    int a;
    cin>>a;
    mpa[a]++;
  }
  rep(i,n){
    int a;
    cin>>a;
    mpb[a]++;
  }
  rep(i,n){
    int a;
    cin>>a;
    mpc[a]++;
  }
  rep(i,n){
    int a;
    cin>>a;
    mpd[a]++;
  }

  auto mpab=f(mpa,mpb);
  auto mpcd=f(mpc,mpd);

  int ans=0;
  for(auto m:mpab){
    //cout<<m.F<<' '<<m.S<<endl;
    if(mpcd.find(v-m.F)==mpcd.end()) continue;
    ans+=m.S*mpcd[v-m.F];
  }

  cout<<ans<<endl;

}