세 상자의 출고 묶음

문제

물류 창고에서는 작은 상자 세 개를 하나의 출고 묶음으로 만들어 운송 장치에 올린다. 오늘 사용할 장치는 묶음의 총무게가 지정된 값과 정확히 같을 때만 작동한다. 창고 담당자는 현재 보관 중인 상자들로 만들 수 있는 출고 묶음이 몇 개인지 확인하려 한다. 창고에는 N개의 상자가 있고, 각 상자에는 1번부터 N번까지 서로 다른 번호가 붙어 있다. i번 상자의 무게는 W_i이다. 출고 묶음 하나를 만들 때는 서로 다른 상자 정확히 세 개를 골라야 한다. 같은 상자를 한 묶음에 두 번 넣을 수 없으며, 두 개 이하 또는 네 개 이상의 상자로 만든 것은 출고 묶음으로 인정하지 않는다. 선택한 세 상자의 무게 합이 목표 무게 T와 같으면 사용할 수 있는 묶음이다. 상자를 고르는 순서는 묶음을 구분하는 기준이 아니다. 예를 들어 1번, 3번, 5번 상자를 선택한 결과는 5번, 1번, 3번 상자를 선택한 결과와 같다. 반면 무게가 같은 상자라도 번호가 다르면 서로 다른 상자이다. 따라서 무게의 구성이 같더라도 선택한 상자 번호의 집합이 다르면 별개의 묶음으로 센다. 이 작업은 실제 출고 계획을 정하는 과정이 아니라 가능한 후보를 세는 과정이다. 서로 다른 후보 묶음에 같은 상자가 포함되어도 되며, 모든 후보를 동시에 만들 수 있어야 한다는 조건은 없다. 또한 세 상자 중 어느 하나의 무게가 목표 무게보다 크면 그 상자를 포함하는 후보는 사용할 수 없다. 가능한 모든 세 상자 선택을 중복 없이 살펴보고, 무게 합이 정확히 T인 후보의 개수를 구한다. 사용할 수 있는 후보가 하나도 없으면 0을 출력한다.

입력

첫째 줄에 정수 N과 T가 공백으로 구분되어 주어진다. 3 ≤ N ≤ 40, 1 ≤ T ≤ 3,000이다.
둘째 줄에 정수 W_1, W_2, ..., W_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ W_i ≤ 1,000이다.

출력

서로 다른 상자 세 개의 무게 합이 T가 되는 선택의 개수를 정수 하나로 출력한다. 선택 순서만 다른 경우는 한 번만 센다.

5 10
2 3 5 4 3

3

4 6
2 2 2 2

4

3 4
2 2 2

0

출처: Devin.KR 자체 제작