Problem C: Only 3-sum

Problem C: Only 3-sum

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 1931  Solved: 236
[Submit][Status][Web Board]

Description

Given \(n\) numbers \(a_1,a_2,...,a_n\), and a lucky number \(m\), please output the number of triple \((i, j, k)\),satisfying \(a_i+a_j+a_k=m (i\lt j\lt k)\).

Input

The first line of the input contains two integers \(n, m(1\le n\le 3000, 1\le m\le 1\ 000\ 000\ 000)\).

The second line contains \(n\) integers \(a_{1},a_{2},...,a_{n}(1\le a_{i}\le 1\ 000\ 000\ 000)\).

Output

Output one integer indicates the answer.

Sample Input

4 9
1 3 5 3

Sample Output

2

HINT

[Submit][Status]