Problem Statement

There are $N$ cards. Each card has two attributes, cost and value; the cost of the $i$-th card is $A_i$ and its value is $B_i$.

You will choose at most $K$ of these $N$ cards, take them with you, and head to the black market. However, the sum of the costs of the cards you take must be at most $L$. The trade succeeds if and only if the sum of the values of the cards you take is at least $P$.

Find the number of ways to choose cards such that the trade can be made successful.

Here, two ways of choosing are considered different if there exists a card that is chosen in one of them and not chosen in the other.

Constraints

• All input values are integers.
• $1 \leq N \leq 34$
• $1 \leq K \leq N$
• $1 \leq L,P \leq 10^9$
• $1 \leq A_i,B_i \leq 10^9$

Input

The input is given from standard input in the following format.

$N$ $K$ $L$ $P$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

Output

Output the answer.

Sample

4 2 4 5
1 2
2 3
3 4
4 5

3

5 5 10 10
2 2
2 2
2 2
2 2
2 2

1

18 5 100 2022
35 890
35 1016
6 9
6 1341
6 398
6 500
6 495
7 406
11 310
11 514
128 321
13 210
13 35
14 99
14 884
18 340
18 1127
18 109

5646