샌안토니오의 유명한 관광상품은 샌안토니오 공원을 margarita 라는 칵테일을 마시면서 걷는 것이다. 다만, margarita 는 여러가지의 재료를 섞어서 만들 수 있으므로, 그 종류가 굉장히 많다. 따라서, 이 문제에서 할 일은 margarita 를 만들 수 있는 가짓 수를 알아내는 것이다.

margarita 를 만드는 조건은 다음과 같다.

• V 개의 재료가 주어진다. 각 재료의 가격이 다를 수 있다. 각 재료는 margarita 를 만들기 위하여 최대 1번을 사용할 수 있다.
• margarita 의 가격제한 D가 주어진다. 즉, D는 재료를 섞어서 만들 때, 사용한 재료의 가격의 총합이 D를 넘어서는 안된다.
• margarita 를 만드는데 사용된 재료의 가격의 총합이 T라고 할 때, D-T의 값으로 아직 이용하지 않은 다른 재료를 살 수 있으면 안된다.

예를들어 보자. 입력 예제에서 주어지는 재료는 V가 6으로 다음표와 같다. 이 때, 가격제한 D는 25다.

재료 A B C D H J
가격 8 9 8 7 16 5

입력

• 첫 줄에 V, D가 주어진다. V는 재료의 수이고, D는 가격제한이다. (1 ≤ V ≤ 1000, 1 ≤ D ≤ 10,000)
• 둘째 줄에는 각 재료의 가격을 나타내는 정수 V개가 주어진다. 각 가격은 10,000 이하의 정수이다.

출력

입출력 예

입력

6 25
8 9 8 7 16 5

출력

15

출처: Greater New York 2006 (원문제보다 V, D 제한을 높였습니다.)
추천: tamaki