선물 할인

면접 대비

시간 제한1초메모리 제한1024 MB

요약

선물 n개의 가격과 예산 b, 최대 a개에 반값 할인을 적용할 때 예산 안에서 살 수 있는 선물의 최대 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

$n$ 개의 선물 가격이 주어졌을 때, $b$ 의 예산으로 최대한 많은 선물을 사려고 한다. 최대 $a$ 개의 선물은 반값에 살 수 있다. 살 수 있는 선물의 최대 개수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다.

입력

첫 번째 줄에 선물의 개수 $n$ ( $1 ≤ n ≤ 100\,000$ ), 예산 $b$ ( $1 ≤ b ≤ 10^9$ ), 반값 할인을 받을 수 있는 최대 선물의 수 $a$ ( $0 ≤ a ≤ n$ )가 공백으로 구분되어 차례로 주어진다. 다음 줄에 $n$ 개의 선물 가격이 공백으로 구분되어 주어진다. 선물 가격은 2 이상 10억 이하의 짝수이다.

출력

예산 안에서 살 수 있는 선물의 최대 개수를 출력한다.

예제2

예제 1
입력
```
6 26 2
4 6 2 10 8 12
```
예상 출력
```
5
```
예제 2
입력
```
6 23 1
4 6 2 12 8 14
```
예상 출력
```
4
```