← 返回题目列表

Codeforces · 590/D

D. 绝密任务

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

祖埃夫上校指挥下的一个绝密军事基地正在等待国防部的视察。根据宪章,每个绝密军事基地都必须包括一支绝密部队,该部队应该……好吧,我们不能告诉你它到底应该做什么,它最终是一支绝密部队。问题是,祖埃夫的基地由于某些原因缺少了这支绝密部队。

上校决定立即处理这个问题,并命令将基地交给他的n名士兵全部排成一排。 Zuev知道左边第i个士兵的说话量等于qi。 Zuev 希望使用队列中最左边的 k 名士兵组成绝密部队,因此他希望他们的总说话量尽可能小(因为部队应该保持绝密)。为了实现这一目标,他将选择一对连续的士兵并交换他们。他打算这样做不超过 s 次。请注意,任何士兵都可以多次参与此类交换。结果发现这个问题很不寻常,祖埃夫上校请你帮忙。

确定队列中前 k 个士兵的最小总语言量是多少,这可以通过执行不超过 s 的两个连续士兵的交换来实现。

输入

输入的第一行包含三个正整数 n、k、s(1 ≤ k ≤ n ≤ 150、1 ≤ s ≤ 109)——分别是该行中的士兵数量、要组建的绝密部队的规模以及连续一对士兵的最大可能交换操作次数。

输入的第二行包含 n 个整数 qi (1 ≤ qi ≤ 1 000 000) — 士兵从左到右排队的言语值。

输出

打印一个整数——绝密部队的最小可能总语言量。

示例

输入 #1

3 2 2
2 4 1

输出 #1

3

输入 #2

5 4 2
10 1 6 2 5

输出 #2

18

输入 #3

5 2 3
3 1 4 2 5

输出 #3

3

注意

在第一个样本中,上校必须交换第二个和第三个士兵,他并不真正需要剩余的交换。最终的士兵顺序是:(2,1,4)。秘密部队的最小可能汇总语言为 3。在第二个示例中,上校将按以下顺序执行交换:

1. (10, 1, 6 — 2, 5)
2. (10, 1, 2, 6 — 5)

生成的士兵顺序为 (10, 1, 2, 5, 6)。

最小可能的汇总语言等于 18。