CF590D.Top Secret Task

A top-secret military base under the command of Colonel Zuev is expecting an inspection from the Ministry of Defence. According to the charter, each top-secret military base must include a top-secret troop that should... well, we cannot tell you exactly what it should do, it is a top secret troop at the end. The problem is that Zuev's base is missing this top-secret troop for some reasons.

The colonel decided to deal with the problem immediately and ordered to line up in a single line all n soldiers of the base entrusted to him. Zuev knows that the loquacity of the i-th soldier from the left is equal to q__i. Zuev wants to form the top-secret troop using k leftmost soldiers in the line, thus he wants their total loquacity to be as small as possible (as the troop should remain top-secret). To achieve this, he is going to choose a pair of consecutive soldiers and swap them. He intends to do so no more than s times. Note that any soldier can be a participant of such swaps for any number of times. The problem turned out to be unusual, and colonel Zuev asked you to help.

Determine, what is the minimum total loquacity of the first k soldiers in the line, that can be achieved by performing no more than s swaps of two consecutive soldiers.

在佐耶夫上校指挥下的一处绝密军事基地即将迎来国防部的检查。根据章程，每处绝密军事基地都必须配备一支绝密部队——至于这支部队具体应执行什么任务……我们无法确切告知，毕竟这是一支名副其实的绝密部队。

问题在于，出于某些原因，佐耶夫上校所辖的基地目前缺少这支绝密部队。

上校决定立即着手解决这一问题，命令将其麾下的全部 $n$ 名士兵排成一列。佐耶夫上校知道，从左往右数第 $i$ 名士兵的多嘴程度（loquacity）为 $q_i$。他计划以队列中最左侧的 $k$ 名士兵组成这支绝密部队，因此希望这 $k$ 名士兵的总多嘴程度尽可能小（毕竟部队须严守绝密）。为达成此目标，他将执行若干次相邻士兵交换操作，且交换次数至多为 $s$ 次。注意：任何士兵均可参与任意多次此类交换。

该问题颇为特殊，佐耶夫上校特此请求你的协助。

请确定：通过至多执行 $s$ 次相邻士兵交换操作，队列最左侧 $k$ 名士兵所能达到的最小总多嘴程度是多少？

The first line of the input contains three positive integers n, k, s (1 ≤ k ≤ n ≤ 150, 1 ≤ s ≤ 109) — the number of soldiers in the line, the size of the top-secret troop to be formed and the maximum possible number of swap operations of the consecutive pair of soldiers, respectively.

The second line of the input contains n integer q__i (1 ≤ q__i ≤ 1 000 000) — the values of loquacity of soldiers in order they follow in line from left to right.

输入的第一行包含三个正整数 $n$、$k$、$s$（$1 ≤ k ≤ n ≤ 150$，$1 ≤ s ≤ 10^9$）—— 分别表示队列中士兵的数量、需组建的绝密小队的规模，以及允许进行的相邻士兵交换操作的最大次数。

输入的第二行包含 $n$ 个整数 $q_i$（$1 ≤ q_i ≤ 1\,000\,000$）—— 表示士兵从左到右在队列中的健谈值。

Print a single integer — the minimum possible total loquacity of the top-secret troop.

输出一个整数——绝密部队的最小可能总饶舌度。

In the first sample Colonel has to swap second and third soldiers, he doesn't really need the remaining swap. The resulting soldiers order is: (2, 1, 4). Minimum possible summary loquacity of the secret troop is 3. In the second sample Colonel will perform swaps in the following order:

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

The resulting soldiers order is (10, 1, 2, 5, 6).

Minimum possible summary loquacity is equal to 18.

在第一个样例中，上校需要交换第二名和第三名士兵，其余的交换操作实际上并不需要。最终的士兵顺序为：$(2, 1, 4)$。秘密部队的最小可能总话痨值为 $3$。在第二个样例中，上校将按以下顺序执行交换操作：

1. $(10, 1, 6 \text{ — } 2, 5)$
2. $(10, 1, 2, 6 \text{ — } 5)$

最终的士兵顺序为 $(10, 1, 2, 5, 6)$。

最小可能总话痨值等于 $18$。