← 返回题目列表

Codeforces · 873/A

A. 家务活

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

Luba今天要做n件家务。第 i 个杂务需要 a 个单位的时间才能完成。保证对于每个 $$i \in [2..n]$$ 满足条件 ai ≥ ai - 1,因此序列已排序。

Luba 也可以非常努力地做一些家务。她可以选择不超过 k 项家务,并在 x 时间单位内完成每项任务,而不是 ai ($${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$)。

Luba 非常负责,所以她必须做所有 n 件家务,现在她想知道做完所有事情所需的最短时间。卢巴不能同时做两件事。

输入

第一行包含三个整数 n、k、x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99) — Luba 必须做的家务数量、她在 x 单位时间内可以做的家务数量以及数字 x 本身。

第二行包含 n 个整数 ai (2 ≤ ai ≤ 100) — Luba 完成第 i 项杂务所需花费的时间。

保证 $${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$,并且对于每个 $$i \in [2..n]$$ ai ≥ ai - 1。

输出

打印一个数字——Luba 完成所有 n 件家务所需的最短时间。

示例

输入 #1

4 2 2
3 6 7 10

输出 #1

13

输入 #2

5 2 1
100 100 100 100 100

输出 #2

302

注意

在第一个示例中,最佳选择是执行第三项和第四项任务,分别在每个任务上花费 x = 2 时间,而不是 a3 和 a4。那么答案是 3 + 6 + 2 + 2 = 13。

在第二个例子中,Luba 可以选择任意两项杂务来花费 x 时间而不是 ai。所以答案是 100·3 + 2·1 = 302。