A Sad Story

Due to an unexpected approach discovered at the contest site.

The constraints and data have been modified; the situation at the training team's mutual testing site is no longer a valid reference.

If you believe your approach is space-efficient but you are receiving MLE, please try replacing the included header files.

Background

Mayflower - Plum

May and July packed their belongings and set off on their own separate paths...

Description

Please note the unconventional memory limit for this problem.

Given $n$ items, with volumes $v_1, v_2, \dots, v_n$ and values $w_1, w_2, \dots, w_n$ respectively.

You need to select some items such that the total volume does not exceed $m$. You will take the selected items with you, and your profit is the sum of the values of these items. Output the maximum possible profit.

Specifically, there is a coefficient $k$ given for each instance, and the data is guaranteed to satisfy the following property:

• If you can first choose a sequence of real numbers $p_1, p_2, \dots, p_n$ where each $p_i \in (0, 1]$. For all items, the volume and value of the $i$-th item are both multiplied by $p_i$, i.e., the volume becomes $p_iv_i$ and the value becomes $p_iw_i$. If you then select items, your maximum profit is $r$.
• In the original problem, assuming your maximum profit is $l$, then $r - l \leq k$.

Input

The first line contains three positive integers $n, m, k$.

The next $n$ lines each contain two positive integers $v_i, w_i$.

Output

A single line containing the answer.

Examples

Input 1

8 20 6
10 6
9 8
6 3
2 5
6 8
3 8
1 9
4 2

Output 1

33

Additional Examples 1~7

See ex_mayflower1~7.in and ex_mayflower1~7.out in the attachment download.

The additional examples satisfy the constraints of the $7$ subtasks of this problem, respectively.

Note

In the example provided in the problem statement, $r$ can be calculated as follows:

• Let $p = [1, \frac 8 9, 1, 1, 1, 1, 1, 1]$, which means for the 2nd item, its volume becomes $8$ and its value becomes $\frac {64} 9$, while other items remain unchanged. Then, select the 2nd, 4th, 5th, 6th, and 7th items. The total volume is $8+2+6+3+1=20$, and the total value is $r = \frac {64} 9 + 5 + 8 + 8 + 9 = \frac {334} 9$. It can be proven that no larger $r$ exists.

$l$ can be calculated as follows:

• Select the 2nd, 5th, 6th, and 7th items. The total volume is $9+6+3+1=19$, and the total value is $l = 8 + 8 + 8 + 9 = 33$. It can be proven that no larger $l$ exists.

Finally, we have $r - l = \frac {37} 9$, and given $k = 6$, the condition $r - l \leq k$ is satisfied.

Constraints

For all data, $1 \leq n \leq 10^4, 1 \leq m \leq 10^9, 1 \leq k \leq 20, 1 \leq v_i \leq 5000, 1 \leq w_i \leq 10^{12}$.

Random Data: For each test case, after $n, m, k$ are given, a set of data is chosen uniformly at random from all possible data sets that satisfy $r - l \leq k$.