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 rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define rept(i,n) for(ll (i)=0;(i)<=(ll)(n);(i)++)
#define reps(i,s,n) for(ll (i)=(s);(i)<(ll)(n);(i)++)
#define repst(i,s,n) for(ll (i)=(s);(i)<=(ll)(n);(i)++)
#define repr(i,n) for(ll (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\???
// .???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????
// ?????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\??????????????????

ll n, v, a[1000], b[1000], c[1000], d[1000], ps[1000000], r;

int main() {
	cin >> n >> v;
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	rep(i,n) cin >> c[i];
	rep(i,n) cin >> d[i];
	rep(i,n) rep(j,n) ps[i*n+j] = a[i] + b[j];
	sort(ps, ps+n*n);
	rep(i,n) rep(j,n) {
		ll t = c[i] + d[j];
		if (t<v) r += upper_bound(ps, ps+n*n, v-t) - lower_bound(ps, ps+n*n, v-t);
	}
	cout << r << ln;
}