H - カンカンマート 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

コンビニ「カンカンマート」では N 個の缶詰が売られています。
i 番目の缶詰は P_i 円で売られており、 T_i = 1 であればその缶詰を開封するのに缶切りが必要で、 T_i = 0 であればその缶詰を開封するのに缶切りは不要です。同じ缶詰を複数個購入することはできません。
缶切りは、1 つ Q 円で何個でも購入できます。1 つの缶切りで K 個の缶詰を開封すると、その缶切りは壊れて使えなくなってしまいます。
あなたは、N 個の缶詰のうち M 個を選び、それらを開けるのに必要な缶切りとともに購入します。このとき必要な最小の合計金額を求めてください。

制約

  • 入力はすべて整数
  • 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)

入力

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

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

出力

必要な最小の合計金額を出力せよ。

入力例 1

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

出力例 1

45

例えば、 3,4,5 番目の缶詰と、缶切りを 1 つ買うことによって必要な最小金額である 45 円を達成できます。これより安いような買い方は存在しないことが示せます。

入力例 2

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

出力例 2

51

缶切りを使って開ける缶詰が 1 つで、 K=5 であっても、缶切りを 1 つ購入する必要があります。

入力例 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

出力例 3

4841818525

答えは非常に大きくなる場合があります。

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A convenience store Can-Can-Mart sells N cans.
The i-th can is sold for P_i yen, and you need a can opener to open it if T_i = 1; you can open it without an opener if T_i = 0.
You can buy any number of openers for Q yen each. An opener can be used to open K cans, after which it gets broken and unusable.
You will choose M of the N cans and buy them, along with openers needed to open them. Find the minimum total amount of money needed for this.

Constraints

  • All values in input 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)

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum total amount of money needed, as an integer.

Sample Input 1

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

Sample Output 1

45

For example, you can buy the 3-rd, 4-th, 5-th cans, and one opener to make the total cost 45 yen. We can show that there is no way that costs less.

Sample Input 2

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

Sample Output 2

51

Even if we have just one can that needs an opener and K = 5, we have to buy one opener.

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

The answer can be enormous.