13004번 - 비밀 임무

BOJ 기지에서는 비밀 임무를 위한 요원들을 골라내고 있다. 그들은 이 임무에 적합한 n명의 요원 후보를 골라내는 데 성공했다. 이 요원들은 모든 점에서 뛰어난 요원들이었지만, 단 하나의 문제가 있었다. 바로 너무 수다스럽다는 것이다.

이 문제를 해결하기 위해, 기지 감독관은 모든 요원 후보들을 한 줄로 세우고, 각 요원 후보들에게 "수다도" a_i를 부여하였다. 그 후, 감독관은 인접한 두 요원 후보를 선택하여 둘의 위치를 바꾸는 작업을 최대 s번 수행할 것이다. 이 작업이 모두 끝난 후, 앞에서부터 k명의 요원 후보들이 요원으로 선택될 것이다.

기지 감독관은 이렇게 선택된 k명의 요원의 "수다도"의 합을 최소로 하길 원한다. 둘의 위치를 바꾸는 작업을 어떤 식으로 수행해야, 이 합을 최소로 만들 수 있을까?

첫 번째 줄에는 세 개의 자연수 n, k, s가 주어진다. (1 ≤ k ≤ n ≤ 150, 1 ≤ s ≤ 10⁹)

다음 줄에는 각 요원의 수다도를 나타내는 정수 n개가 주어진다. (1 ≤ q_i ≤ 1,000,000)

처음 k명의 요원의 수다도의 합의 최솟값을 출력한다.

1번째 입력은 2,3번째 요원을 한 번 바꾸면 된다.

2번째 입력은 3,4번째 => 4,5번째 순서로 2번 바꾸면 된다.

3번째 입력은 1,2번째 => 3,4번째 => 2,3번째 순서로 3번 바꾸면 된다.