시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)301846633.000%

문제

도도는 주방장이다. 총 $K$개의 요리가 준비되는 최소 시간을 구해야 한다.

각각의 요리사는 자신만의 음식 조리 시간이 있다. 음식 조리 시간은 음식 하나를 만들 때 걸리는 시간이다.

도도는 요리사에게 격려를 해줄 수 있다. 격려받은 요리사는 영구적으로 음식 조리 시간이 1초 감소한다.

도도는 한 요리사에게 여러 번 격려할 수 있고, 요리사의 음식 조리 시간을 1초 미만으로 줄일 수는 없다.

도도를 위해 요리에 걸리는 최소 시간을 출력하는 프로그램을 만들어 보자.

입력

첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다.

둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어진다. $i$번째로 주어지는 수 $A_i$는 $i$번째 요리사의 음식 조리 시간이다. ($1 \le i \le N$, $1 \le A_i \le 1\,000\,000$)

출력

첫째 줄에 $K$개의 음식 조리가 완료되는 최소 시간을 출력한다.

예제 입력 1

3 6 2
1 2 3

예제 출력 1

3

예제 입력 2

2 204 1
100 101

예제 출력 2

10200

예제 입력 3

2 200 1
100 101

예제 출력 3

9999