31264번 - 사격 서브태스크

문제

성현이네 부대의 24-1분기 사격 훈련이 시작되었다!

성현이네 부대의 사격 훈련장에는 $N$개의 표적이 있으며, 그중 $i$번째 표적의 점수는 $s_i$이다. 점수가 $s_i$인 표적을 맞히기 위해선 사격 실력이 최소 $s_i$ 이상이어야 한다. 만약 해당 표적을 성공적으로 맞혔다면, 표적의 점수만큼 사격 점수를 획득하며 사격 실력도 동일한 만큼 증가한다.

이번 사격 훈련에서는 최대 $M$번 사격할 수 있으며, 성현이가 진급에 성공하기 위해서는 획득한 사격 점수의 총합이 $A$점 이상이어야 한다.

사격 훈련을 시작하기 전 초기 사격 점수는 0ドル$점이다. 성현이는 항상 자신이 맞힐 수 있는 표적 중 얻을 수 있는 사격 점수가 가장 높은 표적을 맞히며, 동일한 표적을 여러 번 맞히는 것도 가능하다.

진급이 절실했던 성현이는 사격 훈련이 시작하기 전 초기 사격 실력이 어느 정도여야 진급에 성공할 수 있을지 궁금해하고 있다. 성현이를 위해, 진급에 성공하기 위한 초기 사격 실력의 최솟값을 구해주자. 항상 진급에 성공할 수 있는 경우만 입력으로 주어진다.

입력

첫 번째 줄에 표적의 개수 $N,ドル 성현이의 최대 사격 횟수 $M$과 진급에 필요한 최소 사격 점수를 나타내는 정수 $A$가 공백으로 구분되어 주어진다.

두 번째 줄에 표적의 점수를 의미하는 $N$개의 정수 $s_1, \cdots, s_n$이 공백으로 구분되어 주어진다.

출력

성현이가 진급할 수 있는 초기 사격 실력의 최솟값을 구하여라.

제한

• 1ドル \le N \le10^ 5$
• 1ドル \le M \le 10^5$
• 1ドル \le s_i \le 10^5$
• 1ドル \le A \le 10^{10}$
• 모든 입력은 정수이다.

서브태스크

힌트