Problem:


Coin Combination 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.

Sample Input 1

3 14
3 1 2
4 8 2
1 2 3
7 3 2

Sample Output 1

9

Sample Input 2

5 4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

625



Sample input:
3 14
3 1 2
4 8 2
1 2 3
7 3 2


Sample output:
9

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
TLE
"""
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 = [-1, 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 += (j-i)

    print(count)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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 = [a+b for a in A for b in B]
    # AB.sort()

    CD = [float('-inf'), float('inf')]
    for i in C:
        for j in D:
           CD.append(i+j)
    CD.sort()
    CD = tuple(CD)

    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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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 = [a+b for a in A for b in B]
    AB.sort()

    CD = [float('-inf'), float('inf')]
    for i in C:
        for j in D:
           CD.append(i+j)
    CD.sort()
    CD = tuple(CD)

    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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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 = [a+b for a in A for b in B]
    #AB.sort()

    CD = [float('-inf'), float('inf')]
    for i in C:
        for j in D:
           CD.append(i+j)
    CD.sort()
    CD = tuple(CD)

    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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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 = [a+b for a in A for b in B]
    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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
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(reverse=True)

ans = 0
for ab in AB:
  target = v - ab
  ans += br(CD, target) - bl(CD, target)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,V = map(int,input().split())
cnt = 0

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = list(map(int,input().split()))

for alist in a:
    for blist in b:
        for clist in c:
            for dlist in d:
                if alist + blist + clist + dlist == V:
                    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""


"""
import sys
from sys import stdin
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 = []
    for i in C:
        for j in D:
           CD.append(i+j)
    CD.sort()

    count = 0
    for ab in AB:
        count += CD.count(V-ab)

    print(count)





if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

if __name__ == '__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)
    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)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

if __name__ == '__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)
    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)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

if __name__ == '__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))

Submission status: Accepted

Solution code:
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))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
TLE
"""
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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
TLE
"""
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)
 
 
if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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 = [a+b for a in A for b in B]
    #AB.sort()

    #CD = [float('-inf'), float('inf')]
    #for i in C:
    #    for j in D:
    #       CD.append(i+j)
    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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
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)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def largestRectangInHistgram(heights):
    stack = [-1]
    maxArea = 0

    for i in range(len(heights)):
        # we are saving indexes in stack that is why we comparing last element in stack
        # with current height to check if last element in stack not bigger then
        # current element
        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)

    # we went through all elements of heights array
    # let's check if we have something left in stack
    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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#!python3

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()))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter


if __name__ == "__main__":
    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)

Submission status: Accepted

Solution code:
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]
    #target2=target1+0.2
    l=bisect.bisect_left(CD,target1)
    h=bisect.bisect_right(CD,target1)
    ####

    ans+=h
    ans-=l
print(ans)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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



#1:combinatorial
#1_A
"""
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n):
    for j in c:
        if i+j <= n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])
"""
#1_B
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
memo = [[] for i in range(w+1)]
for i in range(w):
    for j in range(n):
        if i+b[j][1] <= w and j not in memo[i]:
            if dp[i+b[j][1]] > dp[i]+b[j][0]:
                continue
            else:
                memo[i+b[j][1]] = memo[i]+[j]
                dp[i+b[j][1]] = dp[i]+b[j][0]

print(max(dp))
"""
#1_C
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
for i in range(w):
    for j in b:
        if i+j[1] <= w:
            dp[i+j[1]] = max(dp[i+j[1]], dp[i]+j[0])
print(dp[w])
"""
#1_D
"""
import bisect

n = int(input())
s = [int(input()) for i in range(n)]
dp = [float("INF") for i in range(n)]
for i in range(n):
    dp[bisect.bisect_left(dp,s[i])] = s[i]
print(bisect.bisect_left(dp,100000000000000))
"""

#1_E
"""
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])
"""
#1_F
"""
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)
"""

#1_G
"""
n,W = map(int,input().split())
k = [list(map(int, input().split())) for i in range(n)]
b = []
for i in range(n):
    for j in range(k[i][2]):
        b.append([k[i][0],k[i][1]])
dp = [0 for i in range(W+1)]

for v,w in b:
    for i in range(W+1):
        if W-i+w <= W:
            dp[W-i+w] = max(dp[W-i+w], dp[W-i]+v)
print(max(dp))
"""

#1_H


#2:permutaion/path


#3:pattern

#3_A
"""
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    dp[i][0] = 1 if c[i][0] == 0 else 0
for i in range(w):
    dp[0][i] = 1 if c[0][i] == 0 else 0
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
ans = 0
for i in dp:
    for j in i:
        ans = max(ans, j)
print(ans**2)
"""

#3_B

#4:counting
#4_A
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)
#5:Twelvedfold_Way

#5_A
"""
n,k = map(int, input().split())
ans = k
for i in range(n-1):
    ans *= k
    ans %= 1000000007
print(ans)
"""

#5_B
"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
if n > k:
    ans = 0
else:
    ans = fact(k)//fact(k-n)
print(ans%1000000007)
"""

#5_C
"""
n,k = map(int, input().split())
if n < k:
    ans = 0
else:
"""

#5_D
"""
n,k = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""

#5_E
"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""
#5_F

#5_G

#5_H

#5_I

#5_J

#5_K

#5_L

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict


def read():
    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()))

def main():
    read()
    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))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)