50036. Pick up Numbers

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to count the number of ways to pick at least $k$ number out of $N$ positive numbers so that the sum of the picked numbers is no more than $M$.

For example, given four numbers $1$, $3$, $5$, and $7$, then there are $6$ ways to pick at least $2$ numbers so that their sum is no more than $10$. The solutions are $\lbrace 1, 3\rbrace , \lbrace 1, 5\rbrace , \lbrace 1, 7\rbrace , \lbrace 3, 5\rbrace , \lbrace 3, 7\rbrace $, and $\lbrace 1, 3, 5\rbrace $.

Input Format

The first line contains three integers: $k$, $N$ and $M$, where $1 \le k \le N$, $1 \le N \le 20$, and $1 \le M \le 5000000$. The second line contains $N$ positive integers; each of them is smaller than $100000$.

Output Format

The number of ways to pick at least $k$ number out of $N$ positive numbers so that the sum of the picked numbers is no more than $M$.

Sample Input

2 4 10
1 3 5 7

Sample Output

6

Discussion