Overcharging Dishes Selection

You are given \(m\) dishes with prices \(a_1, a_2, \dots, a_m\) (in dollars). A customer originally planned to spend \(n\) dollars. However, after ordering, he is asked to reselect exactly \(r\) dishes from the \(m\) available dishes. Your task is to count the number of ways to choose \(r\) dishes such that the total cost exceeds \(n\) dollars.

Input Details:

• The first line contains three integers: \(m\), \(n\), and \(r\), where \(m\) is the total number of dishes, \(n\) is the budget threshold, and \(r\) is the number of dishes to be reselected.
• The second line contains \(m\) space-separated integers \(a_1, a_2, \dots, a_m\) representing the cost of each dish.

Output Details:

• Output a single integer, the number of ways to select \(r\) dishes such that their total cost is greater than \(n\) dollars.

inputFormat

The input contains two lines. The first line contains three integers \(m\), \(n\), and \(r\). The second line contains \(m\) integers \(a_1, a_2, \dots, a_m\) separated by spaces.

outputFormat

Output a single integer representing the count of valid selection schemes where the total cost of the chosen \(r\) dishes exceeds \(n\).

sample

3 10 2
5 10 15

3