시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1890 | 442 | 341 | 25.486% |
$n$개의 선물 가격이 주어졌을 때, $b$의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대 $a$개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다.
입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 $a$ ($0 ≤ a ≤ n$)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 $n$개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 $2$이상 $10$억 이하의 값을 갖으며, 항상 짝수로 주어진다.
출력은 표준출력을 사용한다. 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.
6 26 2 4 6 2 10 8 12
5
6 23 1 4 6 2 12 8 14
4