In this problem you are given a sequence of $N$ positive integers $S[1],S[2],\dots,S[N]$. In addition you are given an integer $T$, and your aim  is to find the number of quadruples $(i,j,k,l)$, such that $1 \le i < j < k < l \le N$, and $S[i] + S[j] + S[k] + S[l] = T$.  That is, the number of ways of picking four numbers from the sequence summing up to $T$.

-----Constraints:-----
For all test cases,
- $1 \le N \le 5000$
- $1 \le T \le 10^6$
- $1 \le S[i] \le 10^9$, for all $i$.
Subtask $1:10\%$
It is guaranteed that $N \le 50$.
Subtask $2:50\%$
It is guaranteed that $N \le 300$.
Subtask $3:40\%$
No additional guarantees.

-----Input Format:-----
There is only one line of input with $N+2$ space separated integers. The first two integers are $N$ and $T$. The next $N$ integers are $S[1],S[2],\dots,S[N]$.

-----Output Format:-----
A single integer which is the number of valid quadruples.

-----Sample Input 1:-----
6 20 3 1 1 2 5 10

-----Sample Output 1:-----
1

-----Explanation 1:-----
The quadruple $(1,4,5,6)$ is valid  because $S[1]+S[4]+S[5]+S[6]=3+2+5+10=20$. You can check that no other quadruple is valid and hence the answer is $1$.

-----Sample Input 2:-----
6 13 1 2 3 4 5 4 

-----Sample Output 2:-----
3

-----Explanation 2:-----
You can verify that the only quadruples that are valid are $(2,3,4,6),(1,3,4,5)$  and $(1,3,5,6)$. Thus, the answer is $3$.

-----Note:-----
As the answer might be large, please use 64 bit integers (long long int in
C/C++ and long in Java) instead of 32 bit int.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from itertools import combinations
a = list(map(int, input().split()))
n = a[0]
t = a[1]
q = list(combinations(a[2:], 4))
total = 0
for i in q:
	if sum(i) == t:
		total += 1
print(total)


from itertools import combinations

def rSubset(arr, r):
	return list(combinations(arr, r))
arr = []
arr = list(map(int, input().split()))
(N, T) = (arr[0], arr[1])
arr.remove(N)
arr.remove(T)
arr = rSubset(arr, 4)
sum = 0
for i in range(0, len(arr)):
	a = list(arr[i])
	if a[0] + a[1] + a[2] + a[3] == T:
		sum += 1
print(sum)


inp = list(map(int, input().split()))
a = inp[2:]
t = inp[1]
q = []
extra = 0

def printCombination(arr, n, r):
	data = [0] * r
	combinationUtil(arr, data, 0, n - 1, 0, r)

def combinationUtil(arr, data, start, end, index, r):
	nonlocal q
	nonlocal extra
	if index == r:
		if sum(data) == t:
			extra += 1
		return
	i = start
	while i <= end and end - i + 1 >= r - index:
		data[index] = arr[i]
		combinationUtil(arr, data, i + 1, end, index + 1, r)
		i += 1
printCombination(a, inp[0], 4)
print(extra)


inp = list(map(int, input().split()))
a = inp[2:]
t = inp[1]
p = []
q = []

def printCombination(arr, n, r):
	data = [0] * r
	combinationUtil(arr, data, 0, n - 1, 0, r)

def combinationUtil(arr, data, start, end, index, r):
	nonlocal q
	nonlocal p
	if index == r:
		p = []
		for j in range(r):
			p.append(data[j])
		q.append(p)
		return
	i = start
	while i <= end and end - i + 1 >= r - index:
		data[index] = arr[i]
		combinationUtil(arr, data, i + 1, end, index + 1, r)
		i += 1
printCombination(a, inp[0], 4)
res = 0
for x in q:
	if t == sum(x):
		res += 1
print(res)


inp = input().split()
inp = [int(q) for q in inp]
a = inp[2:]
t = inp[1]
tmp = a
tmp.sort(reverse=True)
p = []
q = []

def printCombination(arr, n, r):
	data = [0] * r
	combinationUtil(arr, data, 0, n - 1, 0, r)

def combinationUtil(arr, data, start, end, index, r):
	nonlocal q
	nonlocal p
	if index == r:
		p = []
		for j in range(r):
			p.append(data[j])
		q.append(p)
		return
	i = start
	while i <= end and end - i + 1 >= r - index:
		data[index] = arr[i]
		combinationUtil(arr, data, i + 1, end, index + 1, r)
		i += 1
printCombination(a, len(a), 4)
res = 0
for x in q:
	if t == sum(x):
		res += 1
print(res)


nums = list(map(int, input().split()))
(n, t) = (nums.pop(0), nums.pop(0))
ways = [1] + [0] * t
nums.sort()
ans = 0
for i in range(2, n):
	if nums[i] > t - 3:
		break
	j = i - 1
	for k in range(0, j):
		if nums[k] + nums[j] > t - 2:
			break
		ways[nums[k] + nums[j]] += 1
	for last in range(i + 1, n):
		if nums[i] + nums[last] > t - 2:
			break
		left = t - nums[i] - nums[last]
		if left > 1:
			ans += ways[left]
print(ans)


from operator import itemgetter
inp = list(map(int, input().split()))
(n, t) = (inp[0], inp[1])
array = inp[2:]
somme = []
for i in range(n - 1):
	for j in range(i + 1, n):
		somme.append((array[i] + array[j], {i, j}))
somme.sort(key=itemgetter(0))
i_end = len(somme) - 1
counter = 0
for i in range(len(somme) - 1):
	while i_end > i and somme[i][0] + somme[i_end][0] > t:
		i_end -= 1
	if i_end == i:
		break
	appo = i_end
	while appo > i and somme[i][0] + somme[appo][0] == t:
		if len(somme[i][1] & somme[appo][1]) == 0:
			counter += 1
		appo -= 1
print(counter // 3)


from collections import defaultdict
l = list(map(int, input().split()))
n = l[0]
t = l[1]
l.pop(0)
l.pop(0)
d = defaultdict(list)
cnt = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		s = l[i] + l[j]
		if d[t - s]:
			x = d[t - s]
			for p in x:
				if p[0] < i and p[0] < i < p[1] < j:
					cnt += 1
		d[s].append([i, j])
print(cnt)


inp = list(map(int, input().split()))
N = inp[0]
T = inp[1]
array = inp[2:]
array.sort()
sums = [0 for i in range(T)]
total = 0
for i in range(N):
	for forward in range(i + 1, N):
		sm = array[i] + array[forward]
		if sm < T:
			total += sums[T - sm]
	for backward in range(i):
		sm = array[i] + array[backward]
		if sm < T:
			sums[sm] += 1
print(total)


x = list(map(int, input().split()))
n = x[0]
t = x[1]
a = x[2:n + 2]
a.sort()
sums = [0] * t
count = 0
for i in range(n):
	for j in range(i + 1, n):
		add = a[i] + a[j]
		if add < t:
			count += sums[t - add]
	for k in range(i):
		add = a[i] + a[k]
		if add < t:
			sums[add] += 1
print(count)


x = list(map(int, input().split()))
(n, t, a) = (x[0], x[1], x[2:])
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			for l in range(k + 1, n):
				if a[i] + a[j] + a[k] + a[l] == t:
					ans += 1
print(ans)


a = list(map(int, input('').strip().split()))
n = a[0]
t = a[1]
del a[0]
del a[0]
a.sort()
res = list()
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			for l in range(k + 1, n):
				if a[i] + a[j] + a[k] + a[l] == t:
					li = list()
					li.append(i)
					li.append(j)
					li.append(k)
					li.append(l)
					if li not in res:
						res.append(li)
				elif a[i] + a[j] + a[k] + a[l] > t:
					break
print(len(res))