Background

(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.

Problem 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