8588: DPL_4_B : Coin Combination Problem II
[Creator : ]
Description
You have $N$ coins each of which has a value $a_i$.
Find the number of combinations that result when you choose $K$ different coins in such a way that the total value of the coins is greater than or equal to $L$ and less than or equal to $R$.
Input
The input is given in the following format.
$N\ K\ L\ R$
$a_1\ a_2\ ...\ a_N$
Output
Print the number of combinations in a line.
Constraints
$1 ≤ K ≤ N ≤ 40$
$1 ≤ a_i ≤ 10^{16}$
$1 ≤ L ≤ R ≤ 10^{16}$
All input values are given in integers
$1 ≤ a_i ≤ 10^{16}$
$1 ≤ L ≤ R ≤ 10^{16}$
All input values are given in integers
Sample 1 Input
2 2 1 9
5 1
Sample 1 Output
1
Sample 2 Input
5 2 7 19
3 5 4 2 2
Sample 2 Output
5