AT_past202104_h カンカンマート

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ Q $ $ P_1 $ $ T_1 $ $ P_2 $ $ T_2 $ $ \vdots $ $ P_N $ $ T_N $

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

### 注意 この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 入力はすべて整数 - $ 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 例えば、 $ 3,4,5 $ 番目の缶詰と、缶切りを $ 1 $ つ買うことによって必要な最小金額である $ 45 $ 円を達成できます。これより安いような買い方は存在しないことが示せます。 ### Sample Explanation 2 缶切りを使って開ける缶詰が $ 1 $ つで、 $ K=5 $ であっても、缶切りを $ 1 $ つ購入する必要があります。 ### Sample Explanation 3 答えは非常に大きくなる場合があります。