分数: 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
答案可能是巨大的。