問題文

$N$ 枚のカードがあります．それぞれのカードにはコストと価値の2つの指標があり，$i$ 番目のカードのコストは $A_i$，価値は $B_i$ です．

あなたは，これら $N$ 枚のカードの中から $K$ 枚以下のカードを選んで持っていき，闇市場に向かいます．ただし，持っていくカードのコストの総和は，$L$ 以下である必要があります．このとき，持っていくカードの価値の総和が $P$ 以上であれば，またそのときに限り，取引が成功します．

取引を成功させることのできるカードの選び方は何通りあるか，求めてください．

なお，「2つの選び方が異なる」とは，「あるカードが存在して，2つの選び方のうちの一方では選ばれており，他方では選ばれていない」ことを指します．

制約

• 入力はすべて整数である．
• $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$

入力

入力は以下の形式で標準入力から与えられる．

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

出力

答えを出力せよ．

サンプル

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