Description

Little Cyan Fish, an inexperienced businessman, recently launched a store named $\textit{Queen's Organic Jewelry}$. This jewelry store houses $n$ gemstones, where the $i$-th gemstone is priced at $w_i$ dollar and has a beauty of $v_i$. Prior to visiting the store, you have $W$ dollars in hand, which you plan to use to purchase gemstones of the greatest possible total beauty.

Interestingly, Little Cyan Fish's store is running a promotion today. Any visitor to the store can select any $k$ gemstones and take them home absolutely free of charge! With this opportunity at hand, you're keen to know the maximum total beauty of gemstones you could obtain with your $W$ dollars, assuming you adopt the optimal strategy.

Please bear in mind that the store stocks only one unit of each gemstone, so you cannot obtain the same gemstone more than once. Also note that you don't have to spend all the money.

Input Format

There is only one test case in each test file.

The first line of the input contains three integers $n$, $W$ and $k$ ($1 \leq n \leq 5 \times 10^3$, $1 \leq W \leq 10^4$, $0 \leq k \leq n$), indicating the total number of gemstones in the store, the amount of money you have and the number of gemstones you can take for free.

For the following $n$ lines, the $i$-th line contains two integers $w_i$ and $v_i$ ($1 \leq w_i \leq W$, $1 \leq v_i \leq 10^9$), indicating the price and the beauty of the $i$-th gemstone.

Output Format

Output one line containing one integer indicating the answer.

4 10 1
9 10
10 1
3 5
5 20

35

5 13 2
5 16
5 28
7 44
8 15
8 41

129

Hint

In the first example, Little Cyan Fish's shop holds $4$ gemstones and you are permitted to take $1$ gemstone for free. One optimal strategy involves taking the first gemstone for free, and purchasing the third and fourth gemstones.

$$\begin{array}{ | c | c | c | c | } \hline \bf{Gemstone} & \bf{Price\ w_i} & \bf{Beauty\ v_i} & \bf{Action} \\ \hline 1 & 9 & 10 & \text{Take for free} \\ \hline 2 & 10 & 1 & / \\ \hline 3 & 3 & 5 & \text{Purchase} \\ \hline 4 & 5 & 20 & \text{Purchase} \\ \hline \end{array}$$