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 INF 99999999
#define FER 0.0000000001

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

struct Edge
{
	int s, t, w;
	Edge(int s,int t,int w):s(s),t(t),w(w){}
	Edge() :Edge(-1, -1, -1) {}
	bool operator<(const Edge& e)const
	{
		return w != e.w ? w < e.w : (s != e.s ? s < e.s : t < e.t);
	}
};


struct P
{
	double x, y;
	P(double x, double y) :x(x), y(y) {}
	P() :P(0, 0) {}
	P operator+(const P& v)const
	{
		return P(x + v.x, y + v.y);
	}
	P operator-(const P& v)const
	{
		return P(x - v.x, y - v.y);
	}
	P operator*(const double v)const
	{
		return P(x*v, y*v);
	}
	bool operator==(const P& v)const
	{
		return abs(x - v.x) <= 0.0000000000001&&abs(y - v.y) <= 0.00000000000001;
	}
	bool operator!=(const P& v)const
	{
		return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
	}

	double dot(const P& v)const
	{
		return x*v.x + y*v.y;
	}
	double cross(const P& v)const
	{
		return x*v.y - y*v.x;
	}
	double length()const
	{
		return sqrt(x*x + y*y);
	}
	double length2()const
	{
		return (x*x + y*y);
	}

	bool operator<(const P& v)const
	{
		return x<v.x || (x == v.x) && y < v.y;
	}
	bool operator>(const P& v)const
	{
		return x>v.x || (x == v.x) && y > v.y;
	}
};

struct Rectangle
{
	int h;
	int p;
	Rectangle(int h,int p):h(h),p(p){}
};

ll a[1000], b[1000], c[1000], d[1000];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	ll V;
	cin >> N >> V;
	for (int i = 0; i < N; i++)cin >> a[i];
	for (int i = 0; i < N; i++)cin >> b[i];
	for (int i = 0; i < N; i++)cin >> c[i];
	for (int i = 0; i < N; i++)cin >> d[i];

	vector<ll> va, vb;
	for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)
	{
		va.push_back(a[i] + b[j]);
		vb.push_back(c[i] + d[j]);
	}

	sort(va.begin(), va.end());
	sort(vb.begin(), vb.end());

	ll ans = 0;
	for (int i = 0; i != va.size(); i++)
	{
		int ub = upper_bound(vb.begin(), vb.end(), V - va[i]) - vb.begin();
		int lb = lower_bound(vb.begin(), vb.end(), V - va[i]) - vb.begin();
		ans += (ub - lb);
	}

	cout << ans << endl;

	return 0;
}