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: interview

Starter code:

Solutions:
# cook your dish here
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)        

# code
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)


# code
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]

# if len(a) < 4:
#     print("0")
#     exit)

# if tmp[0] + tmp[1] + tmp[2] + tmp[3] < t or tmp[-1] + tmp[-2] + tmp[-3] + tmp[-4] > t:
#     print("0")
#     return

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)


inp = input().split()

inp = [int(q) for q in inp]
a = inp[2::]
t = inp[1]

tmp = a
tmp.sort(reverse=True)

# if len(a) < 4:
#     print("0")
#     exit)

# if tmp[0] + tmp[1] + tmp[2] + tmp[3] < t or tmp[-1] + tmp[-2] + tmp[-3] + tmp[-4] > t:
#     print("0")
#     return

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)


inp = input().split()

inp = [int(q) for q in inp]
a = inp[2::]
t = inp[1]

tmp = a
tmp.sort(reverse=True)

# if len(a) < 4:
#     print("0")
#     exit)

# if tmp[0] + tmp[1] + tmp[2] + tmp[3] < t or tmp[-1] + tmp[-2] + tmp[-3] + tmp[-4] > t:
#     print("0")
#     return

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 = []
for x in q:
    if t == sum(x):
        res.append(x)

print(len(res))


inp = input().split()

inp = [int(q) for q in inp]
a = inp[2::]
t = inp[1]

tmp = a
tmp.sort(reverse=True)

# if len(a) < 4:
#     print("0")
#     exit)

# if tmp[0] + tmp[1] + tmp[2] + tmp[3] < t or tmp[-1] + tmp[-2] + tmp[-3] + tmp[-4] > t:
#     print("0")
#     return

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 = []
for x in q:
    if t == sum(x):
        res.append(x)

print(len(res))


# cook your dish here
'''
from operator import itemgetter
inp=list(map(int, input().split()))
n, t = inp[0], inp[1]
array=inp[2:]
array.sort()
freq={}
for el in array:
    if el not in freq:
        freq[el]=1 
    else:
        freq[el]+=1
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
computed={}
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
    if somme[i][0]+somme[i_end][0]==t and len(somme[i][1]&somme[i_end][1])==0:
        id_start, i_mid1, i_mid2, id_end = sorted(somme[i][1]|somme[i_end][1])
        if (array[id_start], array[i_mid1], array[i_mid2], array[id_end]) not in computed:
            if array[id_start]==array[id_end]:
                appo=freq[array[id_start]]
                counter+=appo*(appo-1)*(appo-2)*(appo-3)//24
            elif array[id_start]==array[i_mid2]:
                appo=freq[array[i_mid1]]
                counter+=appo*(appo-1)*(appo-2)*freq[array[id_end]]//6
            elif array[id_end]==array[i_mid1]:
                appo=freq[array[i_mid1]]
                counter+=appo*(appo-1)*(appo-2)*freq[array[id_start]]//6
            elif array[id_start]==array[i_mid1] and array[id_end]==array[i_mid2]:
                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*(freq[array[i_mid2]]-1)//4
            elif array[id_start]==array[i_mid1]:
                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*freq[array[id_end]]//2
            elif array[id_end]==array[i_mid2]:
                counter+=freq[array[i_mid2]]*(freq[array[i_mid2]]-1)*freq[array[i_mid1]]*freq[array[id_start]]//2
            else:
                counter+=freq[array[id_start]]*freq[array[id_end]]*freq[array[i_mid1]]*freq[array[i_mid2]]
            computed[(array[id_start], array[i_mid1], array[i_mid2], array[id_end])]=1
print(counter)

array.sort()
freq={}
for el in array:
    if el not in freq:
        freq[el]=1 
    else:
        freq[el]+=1
counter=0
id_start=0
id_end=n-1
computed={}
for id_start in range(n-3):
    while id_end>id_start+2 and t-array[id_start]-array[id_end]<array[id_start+1]+array[id_start+2]:
        id_end-=1
    if id_end==id_start+2:
        break
    t_new=t-array[id_start]-array[id_end]
    i_mid2=id_end-1
    for i_mid1 in range(id_start+1, id_end-1):
        print(array[id_start], array[i_mid1], array[i_mid2], array[id_end])
        while i_mid2>i_mid1 and array[i_mid1]+array[i_mid2]>t_new:
            i_mid2-=1 
        if i_mid2==i_mid1:
            break
        if array[i_mid1]+array[i_mid2]==t_new and (array[id_start], array[i_mid1], array[i_mid2], array[id_end]) not in computed:
            if array[id_start]==array[id_end]:
                appo=freq[array[id_start]]
                counter+=appo*(appo-1)*(appo-2)*(appo-3)//24
            elif array[id_start]==array[i_mid2]:
                appo=freq[array[i_mid1]]
                counter+=appo*(appo-1)*(appo-2)*freq[array[id_end]]//6
            elif array[id_end]==array[i_mid1]:
                appo=freq[array[i_mid1]]
                counter+=appo*(appo-1)*(appo-2)*freq[array[id_start]]//6
            elif array[id_start]==array[i_mid1] and array[id_end]==array[i_mid2]:
                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*(freq[array[i_mid2]]-1)//4
            elif array[id_start]==array[i_mid1]:
                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*freq[array[id_end]]//2
            elif array[id_end]==array[i_mid2]:
                counter+=freq[array[i_mid2]]*(freq[array[i_mid2]]-1)*freq[array[i_mid1]]*freq[array[id_start]]//2
            else:
                counter+=freq[array[id_start]]*freq[array[id_end]]*freq[array[i_mid1]]*freq[array[i_mid2]]
            computed[(array[id_start], array[i_mid1], array[i_mid2], array[id_end])]=1
print(counter)
'''

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)

# cook your dish here
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)

# cook your dish here
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)
        
    


# cook your dish here
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)

# cook your dish here
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 = 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)


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)


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)

# cook your dish here
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))

# cook your dish here
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)
print(len(res))

# cook your dish here
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)

# cook your dish here
x = list(map(int,input().split()))
n = x[0]
t = x[1]
a = x[2:n+2]
count = 0
for i in range(3,n,1):
    for j in range(2,i,1):
        for k in range(1,j,1):
            for l in range(k):
                #print(a[i] + a[j] + a[k] + a[l])
                if a[i] + a[j] + a[k] + a[l] == t:
                    #print(a[i] + a[j] + a[k] + a[l])
                    count += 1
print(count)

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)

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)