← 목록으로

세 수의 합

N장의 카드가 있다. 각각의 카드에는 서로 다른 정수가 쓰여 있어서, 모두 N개의 서로 다른 정수가 주어져 있다. 이 정수들을 차례로 A[1], A[2], A[3], ..., A[N]이라고 하자. 여러분이 할 일은, 정수 W가 주어졌을 때, 이 카드 중 서로 다른 세 장을 골라서 여기에 쓰여진 세 수의 합이 W가 되는 경우가 몇 가지가 있는 지 알아내는 것이다.

예를 들어, N=6이고 다음과 같이 여섯 개의 정수들이 주어졌다고 하자.

3 2 11 5 7 13

만약 W=15로 주어졌다면, 이 중 3, 5, 7을 고르면 3+5+7=15이므로 조건을 만족하고, 다른 방법으로 15를 만들 수는 없으므로 세 수의 합이 15가 되는 경우는 총 1가지이다. 만약 W=28로 주어졌다면, 어떤 세 수를 고르더라도 합이 28이 되는 경우를 만들 수 없으므로 세 수의 합이 28이 되는 경우는 총 0가지이다.

N, W, A[1], A[2], ..., A[N]이 주어졌을 때 A[1], A[2], ..., A[N] 중 서로 다른 세 수의 합이 W가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 두 정수 N, W가 주어진다. N은 주어지는 서로 다른 정수의 개수이며, W는 이 중 서로 다른 세 수를 더해서 만들고 싶은 합에 해당하는 수이다. 문제의 정의상 3 ≤ N ≤ 5,000, 6 ≤ W ≤ 3,000,000,000을 만족한다. 두번째 줄에는 N개의 서로 다른 정수 A[1], A[2], A[3], ..., A[N]이 주어진다. 이 수들은 각각 1 이상 1,000,000,000 이하의 범위에 있다.

출력 형식

출력은 한 줄로 구성된다. 첫 줄에는 주어진 A[1], A[2], ..., A[N] 중 서로 다른 세 수를 골라서 이 수의 합이 W가 되게 만들 수 있는 가짓수를 출력한다. 만약 합이 W가 되게 할 수 없다면, 0을 출력한다.

입력 예제 1

6 15
3 2 11 5 7 13

출력 예제 1

1

입력 예제 2

3 6
1 2 3

출력 예제 2

1

입력 예제 3

7 10
1 2 3 4 5 6 7

출력 예제 3

4

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설