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 a i , b i , c i and d i 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 ≤ a i , b i , c i , d i ≤ 10 16  1 ≤ V ≤ 10 16  All input values are given in integers  Input The input is given in the following format.  N  V  a 1  a 2 ... a N  b 1  b 2 ... b N  c 1  c 2 ... c N  d 1  d 2 ... d N  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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):

"""
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:])

Solution (Python):

"""
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:])

Solution (Python):

"""
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 = [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)


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

Solution (Python):

"""
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:])

Solution (Python):
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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):


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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):

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, 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])
"""

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

"""
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])
"""

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


"""
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])
"""

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


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










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





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,k = map(int, input().split())
ans = k
for i in range(n-1):
    ans *= k
    ans %= 1000000007
print(ans)
"""


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


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


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


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

Solution (Python):
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)

Solution (Python):
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)