{"raw_statement":[{"iden":"statement","content":"Luba has to do _n_ chores today. _i_\\-th chore takes _a__i_ units of time to complete. It is guaranteed that for every the condition _a__i_ ≥ _a__i_ - 1 is met, so the sequence is sorted.\n\nAlso Luba can work really hard on some chores. She can choose not more than _k_ any chores and do each of them in _x_ units of time instead of _a__i_ ().\n\nLuba is very responsible, so she has to do all _n_ chores, and now she wants to know the minimum time she needs to do everything. Luba cannot do two chores simultaneously."},{"iden":"input","content":"The first line contains three integers _n_, _k_, _x_ (1 ≤ _k_ ≤ _n_ ≤ 100, 1 ≤ _x_ ≤ 99) — the number of chores Luba has to do, the number of chores she can do in _x_ units of time, and the number _x_ itself.\n\nThe second line contains _n_ integer numbers _a__i_ (2 ≤ _a__i_ ≤ 100) — the time Luba has to spend to do _i_\\-th chore.\n\nIt is guaranteed that , and for each _a__i_ ≥ _a__i_ - 1."},{"iden":"output","content":"Print one number — minimum time Luba needs to do all _n_ chores."},{"iden":"examples","content":"Input\n\n4 2 2\n3 6 7 10\n\nOutput\n\n13\n\nInput\n\n5 2 1\n100 100 100 100 100\n\nOutput\n\n302"},{"iden":"note","content":"In the first example the best option would be to do the third and the fourth chore, spending _x_ = 2 time on each instead of _a_3 and _a_4, respectively. Then the answer is 3 + 6 + 2 + 2 = 13.\n\nIn the second example Luba can choose any two chores to spend _x_ time on them instead of _a__i_. So the answer is 100·3 + 2·1 = 302."}],"translated_statement":[{"iden":"statement","content":"Luba 今天需要完成 #cf_span[n] 项家务。第 #cf_span[i] 项家务需要 #cf_span[ai] 单位时间完成。保证对于每个 $i$，条件 $a_i \\geq a_{i-1}$ 成立，因此序列是有序的。\n\n此外，Luba 可以非常努力地完成某些家务。她可以选择至多 #cf_span[k] 项家务，将每项的完成时间从 #cf_span[ai] 改为 #cf_span[x]（$1 \\leq x \\leq 99$）。\n\nLuba 非常负责任，她必须完成所有 #cf_span[n] 项家务，现在她想知道完成所有家务所需的最少时间。Luba 不能同时进行两项家务。\n\n第一行包含三个整数 #cf_span[n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99]) —— Luba 需要完成的家务数量、她可以以 #cf_span[x] 单位时间完成的家务数量，以及数值 #cf_span[x] 本身。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai (2 ≤ ai ≤ 100)] —— Luba 完成第 #cf_span[i] 项家务所需的时间。\n\n保证 $a_1 \\geq 2$，且对每个 $i$ 都有 $a_i \\geq a_{i-1}$。\n\n请输出一个数 —— Luba 完成所有 #cf_span[n] 项家务所需的最少时间。\n\n在第一个例子中，最佳方案是完成第三项和第四项家务，每项花费 #cf_span[x = 2] 的时间，而不是 #cf_span[a3] 和 #cf_span[a4]。此时答案为 #cf_span[3 + 6 + 2 + 2 = 13]。\n\n在第二个例子中，Luba 可以任选两项家务，每项花费 #cf_span[x] 的时间代替 #cf_span[ai]。因此答案为 #cf_span[100·3 + 2·1 = 302]。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99]) —— Luba 需要完成的家务数量、她可以以 #cf_span[x] 单位时间完成的家务数量，以及数值 #cf_span[x] 本身。第二行包含 #cf_span[n] 个整数 #cf_span[ai (2 ≤ ai ≤ 100)] —— Luba 完成第 #cf_span[i] 项家务所需的时间。保证 $a_1 \\geq 2$，且对每个 $i$ 都有 $a_i \\geq a_{i-1}$。"},{"iden":"output","content":"请输出一个数 —— Luba 完成所有 #cf_span[n] 项家务所需的最少时间。"},{"iden":"examples","content":"输入4 2 23 6 7 10输出13输入5 2 1100 100 100 100 100输出302"},{"iden":"note","content":"在第一个例子中，最佳方案是完成第三项和第四项家务，每项花费 #cf_span[x = 2] 的时间，而不是 #cf_span[a3] 和 #cf_span[a4]。此时答案为 #cf_span[3 + 6 + 2 + 2 = 13]。在第二个例子中，Luba 可以任选两项家务，每项花费 #cf_span[x] 的时间代替 #cf_span[ai]。因此答案为 #cf_span[100·3 + 2·1 = 302]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k, x \\in \\mathbb{Z}^+ $ be given integers with $ 1 \\leq k \\leq n \\leq 100 $, $ 1 \\leq x \\leq 99 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a non-decreasing sequence of integers with $ 2 \\leq a_i \\leq 100 $ for all $ i $, i.e., $ a_i \\geq a_{i-1} $ for $ i = 2, \\dots, n $.\n\n**Constraints**  \n1. $ 1 \\leq k \\leq n \\leq 100 $  \n2. $ 1 \\leq x \\leq 99 $  \n3. $ 2 \\leq a_1 \\leq a_2 \\leq \\dots \\leq a_n \\leq 100 $\n\n**Objective**  \nMinimize the total time to complete all $ n $ chores, where at most $ k $ chores can be completed in $ x $ time units instead of their original time $ a_i $.  \nThe minimal total time is:  \n$$\n\\min_{S \\subseteq \\{1, \\dots, n\\},\\ |S| \\leq k} \\left( \\sum_{i=1}^n \\begin{cases} x & \\text{if } i \\in S \\\\ a_i & \\text{if } i \\notin S \\end{cases} \\right)\n$$  \nEquivalently:  \n$$\n\\sum_{i=1}^n a_i - \\sum_{i \\in S} (a_i - x)\n$$  \nwhere $ S $ is a subset of at most $ k $ indices maximizing $ \\sum_{i \\in S} (a_i - x) $.  \nSince $ A $ is non-decreasing, the optimal $ S $ consists of the $ \\min(k, n) $ largest $ a_i $'s for which $ a_i > x $.","simple_statement":null,"has_page_source":false}