← 返回题目列表

AtCoder · past202104_h

H. 罐罐超市

中文机器翻译题面 查看原题

分数: 6 点

警告

2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

一家便利店 Can-Can-Mart 出售 N 罐头。
的 i第罐售价为 P_i 日元,并且您需要开罐器才能打开它,如果 T_i = 1;您可以在没有开启器的情况下打开它 T_i = 0.
您可以购买任意数量的开瓶器 Q 日元各。可以使用开启器来打开 K 罐头,此后它会损坏且无法使用。
您将选择 M 的 N 罐头并购买它们,以及打开它们所需的开瓶器。找出为此所需的最低总金额。

约束

  • 输入中的所有值都是整数。
  • 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-rd, 4-th, 5第一个罐子和一个开瓶器构成总成本 45 日元。我们可以证明,没有任何方法可以降低成本。


示例输入 2

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

示例输出 2

51

即使我们只有一罐需要开瓶器并且 K = 5,我们必须买一把开瓶器。


示例输入 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

答案可能是巨大的。