Problem Description

At the convenience store "Cankan Mart", there are $ N $ cans for sale.
The $ i $ th can is sold for $ P_i $ yen, and if $ T_i = 1 $, a can opener is required to open it, while if $ T_i = 0 $, a can opener is not needed. Multiple purchases of the same can are not allowed.
Can openers can be purchased for $ Q $ yen each, and any number of them can be bought. Each can opener can open $ K $ cans, after which it breaks and cannot be used anymore.
You will choose $ M $ out of the $ N $ cans and purchase them along with the necessary can openers. Find the minimum total amount required for this purchase.

Input Format

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

$ N $ $ M $ $ K $ $ Q $ $ P_1 $ $ T_1 $ $ P_2 $ $ T_2 $ $\vdots$ $ P_N $ $ T_N $

Output Format

Output the minimum total amount required.

Sample Input and Output

Sample Input #1

6 3 2 10
15 1
25 0
20 0
10 1
5 1
20 0

Sample Output #1

45

Sample Input #2

5 2 5 40
120 0
1 1
90 0
10 0
50 0

Sample Output #2

51

Sample Input #3

16 9 1 631593942
758234071 1
872232933 0
928146137 0
141777768 0
339097211 1
590423762 1
656886697 1
164443392 0
181259343 0
509224290 0
973377384 0
934014075 1
167877698 1
549037938 0
94228809 1
898548470 0

Sample Output #3

4841818525

Notes/Hints

Constraints

• All inputs are integers
• $1 \le M \le N \le 10^5$
• $1 \le K \le N$
• $1 \le Q \le 10^9$
• $1 \le P_i \le 10^9$, $T_i \in \{0,1\}$ $(1 \le i \le N)$

Sample Explanation 1

For example, by buying the 3rd, 4th, and 5th cans and one can opener, you can achieve the minimum amount of 45 yen. It can be shown that there is no cheaper way to buy them.

Sample Explanation 2

Even though there is only one can that needs a can opener and $ K = 5 $, you still need to buy one can opener.

Sample Explanation 3

The answer can be very large.

见题面 Input 部分

见题面 Output 部分