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>

# define F first
# define S second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput (string in = "s") {
  if (fopen (in.c_str(), "r"))
    freopen (in.c_str(), "r", stdin);
  else
    cerr << "Input file not found" << endl;
}                
const int N = 1e3 + 1;
int n;

ll a[4][N];

ll V;

int main()
{                
  //localInput();
  Read_rap ();
  cin >> n >> V;
  for (int i = 0; i < 4; i++)
  	for (int j = 1; j <= n; j++)
  		cin >> a[i][j];

 	vec<ll> s;       
  for (int i = 1; i <= n; i++)
  	for (int j = 1; j <= n; j++)
  		s.pb (a[0][i] + a[1][j]);

  sort (s.begin(), s.end());
  ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ll rem = V - (a[2][i] + a[3][j]);
			ans += upper_bound (s.begin(), s.end(), rem) - lower_bound (s.begin(), s.end(), rem);
		}
	}	
		

	cout << ans; 
	cout << endl;

  return 0;
}










// Coded by Z..