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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
//N^4的dp，折半变为N^2logN

#define NUM 1005

enum Type{
	A,
	B,
	C,
	D,
};

int N;
ll V;
ll input[NUM][4];
//Type type_array[4] = {A,B,C,D};
map<ll,ll> AB,CD;

int main(){

	scanf("%d %lld",&N,&V);
    
	for(int i = 0; i < 4; i++){
		for(int k = 0; k < N; k++){
			scanf("%lld",&input[k][i]);
		} 
	}

	//AとBの組合わせ
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			AB[input[i][A]+input[k][B]]++;
		}
	}

	//CとDの組合せ
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			CD[input[i][C]+input[k][D]]++;
		}
	}

	ll ans = 0;
	map<ll,ll>::iterator it = AB.begin();

	ll num_AB,num_CD;

	while (it != AB.end()){
	   num_AB = it->first;
	   num_CD = V-num_AB;
	   ans += AB[num_AB]*CD[num_CD];
	   it++;
	}

	printf("%lld\n",ans);

	return 0;
}