시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 30 6 6 20.690%

문제

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

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

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

입력

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

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

출력

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

예제 입력 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

힌트

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

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

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