항공권 할인권 배분

문제

여행 일정 관리 서비스에서 여러 구간의 항공권을 한 번에 결제하려 한다. 이용자는 이미 필요한 항공권 N장을 골랐으며, 각 항공권의 할인 전 가격도 확정되어 있다. 모든 항공권을 반드시 구매해야 하므로 일부 항공권을 결제 대상에서 제외하거나 다른 항공권으로 바꿀 수는 없다. 이용자는 같은 종류의 할인권 K장을 가지고 있다. 할인권 한 장을 항공권 한 장에 적용하면 그 항공권의 가격이 D만큼 내려간다. 다만 할인 후 가격이 음수가 되지는 않는다. 따라서 가격이 D보다 작은 항공권에 할인권을 적용하면 그 항공권의 결제 금액은 0이 된다. 할인권의 남은 할인 금액을 다른 항공권으로 넘길 수는 없다. 각 항공권에는 할인권을 최대 한 장만 적용할 수 있고, 각 할인권도 한 번만 사용할 수 있다. 할인권을 적용하지 않은 항공권은 원래 가격을 그대로 지불한다. 할인권을 전부 사용할 필요는 없으며, 사용하지 않은 할인권은 이번 결제 금액에 영향을 주지 않는다. 항공권을 처리하는 순서에 따른 수수료나 추가 할인은 없다. 예를 들어 가격이 3인 항공권에 할인 금액이 7인 할인권을 사용하면 실제로 줄어드는 금액은 3이다. 반면 가격이 10인 항공권에 같은 할인권을 사용하면 실제로 줄어드는 금액은 7이다. 할인권을 어느 항공권에 배분하는지에 따라 전체 결제 금액이 달라질 수 있다. 서비스는 가능한 할인권 배분 중 전체 결제 금액이 가장 작은 배분을 사용한다. 같은 최소 금액을 만드는 배분이 여러 개이면 어느 배분을 선택해도 된다. 선택한 항공권이나 사용한 할인권의 수는 출력하지 않는다. 모든 가격과 할인 금액은 정수이며, 주어진 항공권 전체를 구매하기 위해 지불해야 하는 최소 금액을 구한다.

입력

첫째 줄에 정수 N, K, D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 0 ≤ K ≤ N, 1 ≤ D ≤ 1,000,000,000이다.
둘째 줄에 각 항공권의 가격을 나타내는 정수 P_1, P_2, …, P_N이 공백으로 구분되어 주어진다. 0 ≤ P_i ≤ 1,000,000,000이다. 가격이 같은 항공권도 서로 다른 항공권이다.

출력

모든 항공권의 최소 결제 금액을 정수 하나로 출력한다. 결제 금액이 0이면 0을 출력한다.

5 2 7
3 12 5 9 0

15

4 4 10
0 2 2 8

0

3 0 4
5 1 6

12

출처: Devin.KR 자체 제작