Description

At Pizza Hut, the God of Love and Sorrow was upset and wanted to rip Yue Luo Wu Ti off. He ordered $m$ dishes, each costing $a_i$ yuan. Yue Luo Wu Ti planned to spend only $n$ yuan, so he asked the God of Love and Sorrow to reselect $r$ dishes from these $m$ dishes.

Still trying to spend more money, he called you and asked you to write a program to tell him in how many ways he can choose $r$ dishes from the $m$ dishes such that the total cost exceeds $n$ yuan.

Input Format

The first line contains three integers $m$, $r$, $n$.

The second line contains $m$ integers, where each $a_i$ is the cost of a dish, separated by spaces.

Output Format

Output a single integer, the total number of valid selections.

5 2 8
1 7 2 5 4

4

Hint

Constraints

For $100\%$ of the testdata, $m \le 30$, $r \le m$, $m \le a_i \le 90$, $n \le 2700$.

Translated by ChatGPT 5