시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 216 58 41 24.848%

문제

농부 존은 새 소들이 필요하다! 그래서 농부 존은 소 시장에 가서 새 소들을 사려고 한다.

농부 존은 돈이 많이 없기 때문에 소들을 최대한 효율적으로 사야 한다. 그래서 농부 존은 M원과 K개의 소 쿠폰을 가지고 소 시장에 나온 N마리의 소들을 최대한 많이 사려고 한다.

소 쿠폰은 소 한 마리당 한 번만 쓸 수 있고, 쓰고 나면 사라진다. i번째 소는 Pi원이고, 쿠폰을 썼을 때는 Ci원이 될 때, 농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.

입력

첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 1014)이 주어진다.

다음 줄부터 Pi (1 ≤ Pi ≤ 109), Ci (1 ≤ Ci ≤ Pi)가 주어진다.

출력

농부 존이 최대로 살 수 있는 소 마릿수를 출력하라.

예제 입력 1

4 1 7
3 2
2 2
8 1
4 3

예제 출력 1

3

힌트

농부 존은 1개의 쿠폰과 7원을 가지고 소 시장에 갔다.

3번째 소에 쿠폰 하나를 쓰고 1,2,3번 소를 산다. (1 + 2 + 3 = 6원)

W3sicHJvYmxlbV9pZCI6IjU4OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMThjIFx1YzBhY1x1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWMwYzggXHVjMThjXHViNGU0XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNCEgXHVhZGY4XHViNzk4XHVjMTFjIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHVjMThjIFx1YzJkY1x1YzdhNVx1YzVkMCBcdWFjMDBcdWMxMWMgXHVjMGM4IFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWMwYWNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1YjNjOFx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjJm5ic3A7XHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YzBhY1x1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7XHVhZGY4XHViNzk4XHVjMTFjIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgTVx1YzZkMFx1YWNmYyBLXHVhYzFjXHVjNzU4IFx1YzE4YyBcdWNmZTBcdWQzZjBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YzE4YyBcdWMyZGNcdWM3YTVcdWM1ZDAgXHViMDk4XHVjNjI4IE5cdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHViNGU0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjIFx1Y2ZlMFx1ZDNmMFx1Yzc0MCBcdWMxOGMgXHVkNTVjIFx1YjljOFx1YjlhY1x1YjJmOSBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzRmOCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM0ZjBcdWFjZTAgXHViMDk4XHViYTc0IFx1YzBhY1x1Yjc3Y1x1YzljNFx1YjJlNC4mbmJzcDtpXHViYzg4XHVjOWY4IFx1YzE4Y1x1YjI5NCBQPHN1Yj5pPFwvc3ViPlx1YzZkMFx1Yzc3NFx1YWNlMCwgXHVjZmUwXHVkM2YwXHVjNzQ0IFx1YzM3Y1x1Yzc0NCBcdWI1NGNcdWIyOTQgQzxzdWI+aTxcL3N1Yj5cdWM2ZDBcdWM3NzQgXHViNDIwIFx1YjU0YywgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVjMGI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjNzU4IFx1YjljOFx1YjliZlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxOGMgXHVjMmRjXHVjN2E1XHVjNWQwIFx1YjA5OFx1YzYyOCBcdWMxOGNcdWI0ZTRcdWM3NTggXHViOWM4XHViOWJmXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyA1MCwwMDApLCBcdWIxOGRcdWJkODAgXHVjODc0XHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZmUwXHVkM2YwXHVjNzU4IFx1YWMxY1x1YzIxOCBLKDEgJmxlOyZuYnNwO0sgJmxlOyBOKSwgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjNjOCBNKDEgJmxlOyBNICZsZTsgMTA8c3VwPjE0PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIFA8c3ViPmk8XC9zdWI+ICgxICZsZTsmbmJzcDtQPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPiksIEM8c3ViPmk8XC9zdWI+ICgxICZsZTsgQzxzdWI+aTxcL3N1Yj4gJmxlOyBQPHN1Yj5pPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NzQgXHVjZDVjXHViMzAwXHViODVjIFx1YzBiNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzE4YyBcdWI5YzhcdWI5YmZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIDFcdWFjMWNcdWM3NTggXHVjZmUwXHVkM2YwXHVhY2ZjIDdcdWM2ZDBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwJm5ic3A7XHVjMThjIFx1YzJkY1x1YzdhNVx1YzVkMCBcdWFjMTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjNcdWJjODhcdWM5ZjggXHVjMThjXHVjNWQwIFx1Y2ZlMFx1ZDNmMCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNGYwXHVhY2UwIDEsMiwzXHViYzg4IFx1YzE4Y1x1Yjk3YyBcdWMwYjBcdWIyZTQuICgxICsgMiArIDMgPSA2XHVjNmQwKTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTg5NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdyBDb3Vwb25zIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBuZWVkcyBuZXcgY293cyEgVGhlcmUgYXJlIE4gY293cyBmb3Igc2FsZSAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCksIGFuZCBGSiBoYXMgdG8gc3BlbmQgbm8gbW9yZSB0aGFuIGhpcyBidWRnZXQgb2YgTSB1bml0cyBvZiBtb25leSAoMSAmbHQ7PSBNICZsdDs9IDEwXjE0KS4gIENvdyBpIGNvc3RzIFBfaSBtb25leSAoMSAmbHQ7PSBQX2kgJmx0Oz0gMTBeOSksIGJ1dCBGSiBoYXMgSyBjb3Vwb25zICgxICZsdDs9IEsgJmx0Oz0gTiksIGFuZCB3aGVuIGhlIHVzZXMgYSBjb3Vwb24gb24gY293IGksIHRoZSBjb3cgY29zdHMgQ19pIGluc3RlYWQgKDEgJmx0Oz0gQ19pICZsdDs9IFBfaSkuIEZKIGNhbiBvbmx5IHVzZSBvbmUgY291cG9uIHBlciBjb3csIG9mIGNvdXJzZS48XC9wPjxwPldoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvd3MgRkogY2FuIGFmZm9yZD88XC9wPiIsImlucHV0IjoiPHVsPjxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiwgSywgYW5kIE0uPFwvbGk+PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdHdvIGludGVnZXJzOiBQX2kgYW5kIENfaS48XC9saT48XC91bD4iLCJvdXRwdXQiOiI8dWw+PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvd3MgRkogY2FuIGFmZm9yZC48XC9saT48XC91bD4iLCJoaW50IjoiPGg0PklucHV0IERldGFpbHM8XC9oND48cD5GSiBoYXMgNCBjb3dzLCAxIGNvdXBvbiwgYW5kIGEgYnVkZ2V0IG9mIDcuPFwvcD48aDQ+T3V0cHV0IERldGFpbHM8XC9oND48cD5GSiB1c2VzIHRoZSBjb3Vwb24gb24gY293IDMgYW5kIGJ1eXMgY293cyAxLCAyLCBhbmQgMywgZm9yIGEgdG90YWwgY29zdCBvZiAzICsgMiArIDEgPSA2LjxcL3A+Iiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO February 2012 Contest > Gold 1번