SBC Hangar

Interview

Time limit2sMemory limit512 MB

Summary

Count the K-element subsets of N distinct weights whose sum lies in [A, B], given that each weight is at least twice the next smaller one.

Level: Medium6 of 10
Topics: Combinatorics, Sorting, Greedy, Math
Solved: No attempts yet

Problem

A small cargo plane from the Sistema Binário de Cargas (SBC) was designed to transport special, secret products. These products are packed in boxes of various weights.

The plane has a safe weight range, within which the aircraft stays stable. More precisely, there is an interval such that if the total weight of the transported boxes falls outside it, the stability of the flight cannot be guaranteed.

All boxes have distinct weights. Also, for any two boxes, the heavier one weighs at least twice as much as the lighter one.

Your task is to determine how many ways one can choose a specified number of boxes to transport on the plane without destabilizing it.

Input

The first line of the input contains two integers, N and K, which represent the number of available boxes and the number of boxes that must be loaded onto the plane, respectively.

The second line of the input contains N integers, separated by a single space, which represent the weights of the boxes.

The third line of the input contains two integers, A and B, which specify the safe weight interval, which is the closed interval [A, B].

All weights given are in the same unit.

Output

The output consists of a single line containing the number of different choices of boxes in the specified quantity that do not put the flight at risk.

Constraints

1 ≤ N ≤ 50.
1 ≤ K ≤ 50.
The weight P of each box lies in the interval 1 ≤ P ≤ 10^18.
1 ≤ A ≤ B ≤ 2 × 10^18.

Examples3

Example 1
Input
```
3 2
10 1 3
4 13
```
Expected output
```
3
```
Example 2
Input
```
4 3
20 10 50 1
21 81
```
Expected output
```
4
```
Example 3
Input
```
6 3
14 70 3 1 6 31
10 74
```
Expected output
```
11
```