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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
from collections import defaultdict
(n, v) = map(int, sys.stdin.readline().split())
a = tuple(map(int, sys.stdin.readline().split()))
b = tuple(map(int, sys.stdin.readline().split()))
c = tuple(map(int, sys.stdin.readline().split()))
d = tuple(map(int, sys.stdin.readline().split()))
mp = defaultdict(int)
ls = []
for val1 in c:
	for val2 in d:
		mp[val1 + val2] += 1
ans = 0
for val1 in a:
	for val2 in b:
		ans += mp[v - val1 - val2]
print(ans)


import sys
from collections import defaultdict
(n, v) = map(int, sys.stdin.readline().split())
a = tuple(map(int, sys.stdin.readline().split()))
b = tuple(map(int, sys.stdin.readline().split()))
c = tuple(map(int, sys.stdin.readline().split()))
d = tuple(map(int, sys.stdin.readline().split()))
mp = defaultdict(int)
for val1 in c:
	for val2 in d:
		mp[val1 + val2] += 1
print(sum((mp[v - val1 - val2] for val1 in a for val2 in b)))


import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline

def main(args):
	(N, V) = map(int, input().split())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	C = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	AB = tuple((a + b for a in A for b in B))
	CD = [c + d for c in C for d in D]
	CD.append(float('-inf'))
	CD.append(float('inf'))
	CD.sort()
	count = 0
	for ab in AB:
		i = bisect_left(CD, V - ab)
		j = bisect_right(CD, V - ab)
		count += j - i
	print(count)
main(sys.argv[1:])


from collections import defaultdict
iim = lambda : map(int, input().rstrip().split())

def resolve():
	(N, V) = iim()
	AN = 4
	A = [list(iim()) for i in range(AN)]

	def dd(a1, a2):
		d = defaultdict(int)
		for i in a1:
			for j in a2:
				x = i + j
				if x < V:
					d[x] += 1
		return d
	(da, db) = (dd(A[0], A[1]), dd(A[2], A[3]))
	print(sum((v * db[V - k] for (k, v) in da.items())))
resolve()


import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline

def main(args):
	(N, V) = map(int, input().split())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	C = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	AB = [a + b for a in A for b in B]
	CD = [c + d for c in C for d in D]
	CD.append(float('-inf'))
	CD.append(float('inf'))
	CD.sort()
	count = 0
	for ab in AB:
		i = bisect_left(CD, V - ab)
		j = bisect_right(CD, V - ab)
		count += max(j - i, 0)
	print(count)
main(sys.argv[1:])


coins = []
line = input()
(n, v) = list(map(int, line.split()))
for _ in range(0, 4):
	line = input()
	c = list(map(int, line.split()))
	coins += [c]

def solve(n, v):
	ab = {}
	for i in range(0, n):
		for j in range(0, n):
			a = coins[0][i] + coins[1][j]
			if a not in ab:
				ab[a] = 1
			else:
				ab[a] += 1
	cd = {}
	low = 10 ** 17
	high = 0
	for i in range(0, n):
		for j in range(0, n):
			a = coins[2][i] + coins[3][j]
			if a not in cd:
				cd[a] = 1
				low = min(low, a)
				high = max(high, a)
			else:
				cd[a] += 1
	ans = 0
	for k in ab:
		if v - k < low or high < v - k:
			continue
		if v - k in cd:
			ans += ab[k] * cd[v - k]
	return ans
print(solve(n, v))


import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline

def main(args):
	(N, V) = map(int, input().split())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	C = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	AB = []
	for i in A:
		for j in B:
			AB.append(i + j)
	AB.sort()
	CD = [float('-inf'), float('inf')]
	for i in C:
		for j in D:
			CD.append(i + j)
	CD.sort()
	count = 0
	for ab in AB:
		i = bisect_left(CD, V - ab)
		j = bisect_right(CD, V - ab)
		count += max(j - i, 0)
	print(count)
main(sys.argv[1:])


from collections import Counter
(N, V) = map(int, input().split())
cnt = 0
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
ab = Counter((ai + bi for ai in a for bi in b))
cd = Counter((ci + di for ci in c for di in d))
cnt = sum((ab[V - i] * t for (i, t) in cd.items() if V - i in ab))
print(cnt)


from collections import defaultdict
import math
import bisect

def LI():
	return list(map(int, input().split()))

def II():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def IIR(n):
	return [II() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]
mod = 1000000007
(n, v) = LI()
a = LI()
b = LI()
c = LI()
d = LI()
p = defaultdict(int)
q = defaultdict(int)
for i in a:
	for j in b:
		if i + j <= v - 2:
			p[i + j] += 1
for i in c:
	for j in d:
		if i + j <= v - 2:
			q[i + j] += 1
ans = 0
for (i, j) in p.items():
	ans += j * q[v - i]
print(ans)


(N, V) = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
D = [int(x) for x in input().split()]
AB = {}
for a in A:
	for b in B:
		AB.setdefault(a + b, 0)
		AB[a + b] += 1
CD = {}
for c in C:
	for d in D:
		CD.setdefault(c + d, 0)
		CD[c + d] += 1
ans = 0
for ab in AB.keys():
	if V - ab in CD:
		ans += AB[ab] * CD[V - ab]
print(ans)


import sys, collections as cl, bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return map(int, input().split())

def onem():
	return int(input())

def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x) - 1):
		if aa == x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a

def jo(x):
	return ' '.join(map(str, x))
(n, v) = m()
a = l()
b = l()
c = l()
d = l()
ab = cl.Counter((aa + bb for aa in a for bb in b))
cd = cl.Counter((cc + dd for cc in c for dd in d))
print(sum((g * cd[v - f] for (f, g) in ab.items() if v - f in cd)))


from bisect import *
(N, V) = map(int, input().split())
boxs = []
for i in range(4):
	boxs.append(list(map(int, input().split())))
pre = [a + b for a in boxs[0] for b in boxs[1]]
af = [c + d for c in boxs[2] for d in boxs[3]]
pre.sort()
af.sort()
ans = 0
for ab in pre:
	target = V - ab
	ans += bisect_right(af, target) - bisect_left(af, target)
print(ans)


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(N, V) = LI()
	a = LI()
	b = LI()
	c = LI()
	d = LI()
	ab = [i + j for (i, j) in itertools.product(a, b)]
	cd = [i + j for (i, j) in itertools.product(c, d)]
	ab.sort()
	cd.sort()
	ans = 0
	for i in ab:
		idx_l = bisect.bisect_left(cd, V - i)
		idx_r = bisect.bisect_right(cd, V - i)
		ans += idx_r - idx_l
	print(ans)
resolve()


from bisect import bisect_left as bl
from bisect import bisect_right as br
(n, v) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
AB = [a + b for a in A for b in B]
CD = [c + d for c in C for d in D]
AB.sort()
CD.sort()
ans = 0
for ab in AB:
	target = v - ab
	ans += br(CD, target) - bl(CD, target)
print(ans)


import sys
from collections import defaultdict
(n, v) = map(int, sys.stdin.readline().split())
a = tuple(map(int, sys.stdin.readline().split()))
b = tuple(map(int, sys.stdin.readline().split()))
c = tuple(map(int, sys.stdin.readline().split()))
d = tuple(map(int, sys.stdin.readline().split()))
mp = defaultdict(int)
for val1 in c:
	for val2 in d:
		mp[val1 + val2] += 1
print(sum((mp[v - val1 - val2] for val1 in a for val2 in b)))


from collections import Counter
(n, v) = map(int, input().split())
(a, b, c, d) = (tuple(map(int, input().split())) for _ in range(4))
ab = Counter((ai + bi for ai in a for bi in b))
cd = Counter((ci + di for ci in c for di in d))
print(sum((t * cd[v - k] for (k, t) in ab.items() if v - k in cd)))


from collections import Counter
(n, v) = map(int, input().split())
(a, b, c, d) = (tuple(map(int, input().split())) for _ in range(4))
ab = [ai + bi for ai in a for bi in b]
cd = [ci + di for ci in c for di in d]
(abc, cdc) = (Counter(ab), Counter(cd))
ans = 0
for (k, t) in abc.items():
	if v - k in cdc:
		ans += t * cdc[v - k]
print(ans)


import bisect
(n, v) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
AB = []
for i in range(n):
	for j in range(n):
		AB.append(A[i] + B[j])
CD = []
for i in range(n):
	for j in range(n):
		CD.append(C[i] + D[j])
AB.sort()
CD.sort()
ans = 0
for i in range(n ** 2):
	target1 = v - AB[i]
	l = bisect.bisect_left(CD, target1)
	h = bisect.bisect_right(CD, target1)
	ans += h
	ans -= l
print(ans)


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import decimal
import queue
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : map(int, sys.stdin.readline().split())
na = lambda : list(map(int, sys.stdin.readline().split()))

def largestRectangInHistgram(heights):
	stack = [-1]
	maxArea = 0
	for i in range(len(heights)):
		while stack[-1] != -1 and heights[stack[-1]] > heights[i]:
			lastElementIndex = stack.pop()
			maxArea = max(maxArea, heights[lastElementIndex] * (i - stack[-1] - 1))
		stack.append(i)
	while stack[-1] != -1:
		lastElementIndex = stack.pop()
		maxArea = max(maxArea, heights[lastElementIndex] * (len(heights) - stack[-1] - 1))
	return maxArea

def main():
	(n, v) = ns()
	a = na()
	b = na()
	c = na()
	d = na()
	pair1 = []
	pair2 = []
	ans = 0
	for ai in a:
		for bi in b:
			pair1.append(ai + bi)
	for ci in c:
		for di in d:
			pair2.append(ci + di)
	pair1.sort()
	pair2.sort()
	p2cnt = collections.Counter(pair2)
	for p in pair1:
		tmp = v - p
		if tmp in p2cnt.keys():
			ans += p2cnt[tmp]
	print(ans)
main()


import sys
from collections import defaultdict

def main():
	(n, v) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	b = list(map(int, sys.stdin.readline().split()))
	c = list(map(int, sys.stdin.readline().split()))
	d = list(map(int, sys.stdin.readline().split()))
	mp = defaultdict(int)
	for val1 in c:
		for val2 in d:
			mp[val1 + val2] += 1
	print(sum((mp[v - val1 - val2] for val1 in a for val2 in b)))
main()


from collections import Counter
(N, V) = map(lambda x: int(x), input().split())
bags = [list(map(lambda x: int(x), input().split())) for _ in range(4)]
merged_0_1 = Counter((v1 + v2 for v1 in bags[0] for v2 in bags[1]))
merged_2_3 = Counter((v1 + v2 for v1 in bags[2] for v2 in bags[3]))
ans = sum((merged_0_1[V - val] * num for (val, num) in merged_2_3.items() if V - val in merged_0_1))
print(ans)


import sys
from collections import defaultdict

def main():
	(n, v) = map(int, sys.stdin.readline().split())
	a = tuple(map(int, sys.stdin.readline().split()))
	b = tuple(map(int, sys.stdin.readline().split()))
	c = tuple(map(int, sys.stdin.readline().split()))
	d = tuple(map(int, sys.stdin.readline().split()))
	mp = defaultdict(int)
	for val1 in c:
		for val2 in d:
			mp[val1 + val2] += 1
	print(sum((mp[v - val1 - val2] for val1 in a for val2 in b)))
main()


import sys, itertools
readline = sys.stdin.readline
write = sys.stdout.write
(N, V) = map(int, input().split())
(*A,) = map(int, input().split())
(*B,) = map(int, input().split())
(*C,) = map(int, input().split())
(*D,) = map(int, input().split())
AB = {}
for (a, b) in itertools.product(A, B):
	AB[a + b] = AB.get(a + b, 0) + 1
key0 = sorted(AB)
CD = {}
for (c, d) in itertools.product(C, D):
	CD[c + d] = CD.get(c + d, 0) + 1
key1 = sorted(CD, reverse=1)
it = iter(key1)
v1 = next(it, None)
ans = 0
for v0 in key0:
	while v1 is not None and v0 + v1 > V:
		v1 = next(it, None)
	if v1 is not None and v0 + v1 == V:
		ans += AB[v0] * CD[v1]
write('%d\n' % ans)


import sys
from collections import defaultdict
(n, v) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))
d = list(map(int, sys.stdin.readline().split()))
mp = defaultdict(int)
ls = []
for val1 in c:
	for val2 in d:
		mp[val1 + val2] += 1
ans = 0
for val1 in a:
	for val2 in b:
		ans += mp[v - val1 - val2]
print(ans)