P1705 Love and Sorrow, Going Too Far

(This problem hides two song titles. Try to find them~~~). Chapter 3 of "The Story of Love and Sorrow, Volume One · heartache." The God of Love and Sorrow says this is ta's sadness index, but it's much better now. The translation is just to give you something to do when you're bored (shit~~~). Although Yue Luo Wu Ti cursed out loud: "I bought a watch last year... a Newman watch...", in the end he still treated the God of Love and Sorrow to a meal at Pizza Hut.

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.

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 a single integer, the total number of valid selections.

### 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