쉬어 가는 시음 순서

문제

한 카페가 새로운 음료를 소개하는 시음 행사를 준비한다. 행사표에는 서로 다른 음료 N개가 1번부터 N번까지 순서대로 적혀 있다. 각 음료에는 시음에 필요한 재료의 양이 정수로 정해져 있다. 같은 양의 재료를 사용하는 음료라도 번호가 다르면 서로 다른 음료다. 담당자는 행사표에서 정확히 K개의 음료를 골라 하나의 시음 구성을 만들려고 한다. 손님이 비슷한 향을 연달아 맛보지 않도록, 행사표에서 번호가 연속한 두 음료를 함께 고를 수 없다. 예를 들어 3번을 골랐다면 2번과 4번을 고를 수 없다. 행사표는 원형이 아니므로 1번과 N번 사이에는 별도의 제한이 없다. 또한 고른 음료에 필요한 재료의 양을 모두 더한 값이 준비된 재료의 양 B 이하여야 한다. 재료가 남는 것은 허용되며, 합이 정확히 B인 구성도 허용된다. 고르지 않은 음료는 재료를 사용하지 않는다. 음료를 제공하는 순서는 행사표의 순서로 고정되어 있으므로, 같은 번호들을 골랐다면 고르는 과정이나 제공 준비 순서가 달라도 같은 구성이다. 가능한 시음 구성의 개수를 구하는 프로그램을 작성한다. 두 구성은 선택한 음료 번호의 집합이 다를 때에만 서로 다르다. 정확히 K개를 고를 수 없거나 재료 제한을 만족하는 구성이 없다면 개수는 0이다. K가 0이면 아무 음료도 고르지 않는 구성을 하나로 센다. 이 구성은 재료를 사용하지 않으므로 항상 재료 제한을 만족한다. 구성 자체를 나열하거나 가장 적은 재료를 사용하는 구성을 찾을 필요는 없다.

입력

첫째 줄에 정수 N, K, B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 24, 0 ≤ K ≤ N, 0 ≤ B ≤ 240이다.
둘째 줄에 각 음료의 재료 사용량을 나타내는 정수 A_1, A_2, …, A_N이 주어진다. 1 ≤ A_i ≤ 10이다.

출력

조건을 모두 만족하는 시음 구성의 개수를 정수 하나로 출력한다. 가능한 구성이 없으면 0을 출력한다.

5 2 7
2 4 3 1 5

4

4 3 40
1 1 1 1

0

3 0 0
4 2 7

1

출처: Devin.KR 자체 제작