시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB189044234125.486%

문제

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

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 $a$ ($0 ≤ a ≤ n$)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 $n$개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 $2$이상 $10$억 이하의 값을 갖으며, 항상 짝수로 주어진다.

출력

출력은 표준출력을 사용한다. 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.

예제 입력 1

6 26 2
4 6 2 10 8 12

예제 출력 1

5

예제 입력 2

6 23 1
4 6 2 12 8 14

예제 출력 2

4
W3sicHJvYmxlbV9pZCI6IjI1OTQ3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHViYjNjXHVkNTYwXHVjNzc4IiwiZGVzY3JpcHRpb24iOiI8cD4kbiRcdWFjMWNcdWM3NTggXHVjMTIwXHViYjNjIFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCAkYiRcdWM3NTggXHVjNjA4XHVjMGIwXHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI5Y2VcdWM3NDAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzBhY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWNkNWNcdWIzMDAgJGEkXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHViYzE4XHVhYzEyIFx1ZDU2MFx1Yzc3OFx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWMwYjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWJiM2NcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZTgsIFx1ZDU1YyBcdWMxMjBcdWJiM2NcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHViYzE4XHVhYzEyIFx1ZDU2MFx1Yzc3OFx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMjBcdWJiM2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICRuJCAoJDEgJmxlOyBuICZsZTsgMTAwXFwsMDAwJCksIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkYiQgKCQxICZsZTsgYiAmbGU7IDEwXjkkKSwgXHViYzE4XHVhYzEyIFx1ZDU2MFx1Yzc3OFx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjMTIwXHViYjNjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICRhJCAoJDAgJmxlOyBhICZsZTsgbiQpXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgJG4kXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzYyBcdWFjMDBcdWFjYTlcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxMjBcdWJiM2MgXHVhYzAwXHVhY2E5XHVjNzQwICQyJFx1Yzc3NFx1YzBjMSAkMTAkXHVjNWI1IFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhYzE2XHVjNzNjXHViYTcwLCBcdWQ1NmRcdWMwYzEgXHVjOWRkXHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3MCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVjMGI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjU5NDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHaWZ0IERpc2NvdW50IiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiB0aGUgcHJpY2VzIG9mICRuJCBnaWZ0cywgd2UgdHJ5IHRvIGJ1eSB0aGUgbWF4aW11bSBudW1iZXIgb2YgZ2lmdHMgd2l0aCB0aGUgYnVkZ2V0IG9mICRiJC4gWW91IHdyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBnaWZ0cyB3aXRoIGEgYnVkZ2V0ICRiJCB5b3UgY2FuIGJ1eSB3aGVuIHlvdSBjYW4gZ2V0IGEgaGFsZi1wcmljZSBkaXNjb3VudCBvbiB1cCB0byAkYSQgZ2lmdHMuIE5vdGUgdGhhdCB5b3UgY2FuIG9ubHkgcmVjZWl2ZSBhIGhhbGYtcHJpY2UgZGlzY291bnQgYXQgbW9zdCBvbmNlIHBlciBnaWZ0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRocmVlIGludGVnZXJzLCAkbiQgKCQxICZsZTsgbiAmbGU7IDEwMFxcLDAwMCQpIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGdpZnRzLCAkYiQgKCQxICZsZTsgYiAmbGU7IDEwXjkkKSByZXByZXNlbnRpbmcgdGhlIGJ1ZGdldCwgYW5kICRhJCAoJDAgJmxlOyBhICZsZTsgbiQpIHJlcHJlc2VudGluZyB0aGUgbWF4aW11bSBudW1iZXIgb2YgZ2lmdHMgZWxpZ2libGUgZm9yIGEgaGFsZi1wcmljZSBkaXNjb3VudC4gVGhlIG5leHQgbGluZSBjb250YWlucyAkbiQgaW50ZWdlcnMgcmVwcmVzZW50aW5nIHRoZSBnaWZ0IHByaWNlcy4gWW91IG1heSBhc3N1bWUgdGhhdCBhbGwgZ2lmdCBwcmljZXMgYXJlIGJldHdlZW4gJDIkIGFuZCAkMTBeOSQgYW5kIGFyZSBldmVuIG51bWJlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG1heGltdW0gbnVtYmVyIG9mIGdpZnRzIHRoYXQgY2FuIGJlIHB1cmNoYXNlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d