문제
에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다.
이 게임에서 초기에 에릭은 당근을 0ドル$개 가지고 있고, $s$가 1ドル$인 상태로 게임을 시작한다.
그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.
- 마우스를 클릭하고 당근을 $s$개 얻는다.
- 정수 $i$$(1 \le i \le N)$를 고르고, 당근 $A_i$개를 지불하여 $i$번째 스피드 효과를 구매한다. 구매 직후, $s$가 $B_i$만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)
게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 $K$초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!
출력
에릭이 게임을 $K$초 플레이한 후 최대로 가지고 있을 수 있는 당근의 개수를 출력한다.
제한
- 1ドル\le N,K\le 100$
- 1ドル\le A_i,B_i\le 50$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 3 | $K \le 2$
|
| 2 | 12 | $N \le 4;$ $K \le 10$
|
| 3 | 20 | $N = 1$
|
| 4 | 65 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMxNDM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmY5XHVhZGZjIFx1ZDA3NFx1YjlhZCBcdWFjOGNcdWM3ODQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzVkMFx1YjlhZFx1Yzc0MCBcdWJjMjlcdWQ1NTkgXHViM2Q5XHVjNTQ4IFx1YjEwOFx1YmIzNCBcdWMyZWNcdWMyZWNcdWQ1NWMgXHViMDk4XHViYTM4XHVjOWMwLCA8c3Ryb25nPlx1YjJmOVx1YWRmYyBcdWQwNzRcdWI5YWQgXHVhYzhjXHVjNzg0PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWMxXHVjODExIFx1YjljY1x1YjRlNFx1YzViNFx1YzExYyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1Y2QwOFx1YWUzMFx1YzVkMCBcdWM1ZDBcdWI5YWRcdWM3NDAgXHViMmY5XHVhZGZjXHVjNzQ0ICQwJFx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCAkcyRcdWFjMDAgJDEkXHVjNzc4IFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVkNmM0LCBcdWI5ZTRcdWNkMDggXHViMmU0XHVjNzRjIFx1YjQ1MCBcdWFjMDBcdWM5YzBcdWM3NTggXHVkNTg5XHViM2Q5IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViOWM4XHVjNmIwXHVjMmE0XHViOTdjIFx1ZDA3NFx1YjlhZFx1ZDU1OFx1YWNlMCBcdWIyZjlcdWFkZmNcdWM3NDQgJHMkXHVhYzFjIFx1YzViYlx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjODE1XHVjMjE4ICRpJCQoMSBcXGxlIGkgXFxsZSBOKSRcdWI5N2MgXHVhY2UwXHViOTc0XHVhY2UwLCBcdWIyZjlcdWFkZmMgJEFfaSRcdWFjMWNcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTU4XHVjNWVjICRpJFx1YmM4OFx1YzlmOCBcdWMyYTRcdWQ1M2NcdWI0ZGMgXHVkNmE4XHVhY2ZjXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU1Y1x1YjJlNC4gXHVhZDZjXHViOWU0IFx1YzljMVx1ZDZjNCwgJHMkXHVhYzAwICRCX2kkXHViOWNjXHVkMDdjIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC4gKFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHVjMmE0XHVkNTNjXHViNGRjIFx1ZDZhOFx1YWNmY1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0IFx1YWM4M1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3UuYWNtaWNwYy5uZXRcL2MwYzliYzVkLTI2MjgtNDNmNy1hNTY0LTk0M2IyODA5NjIwMFwvJUVCJThCJUI5JUVBJUI3JUJDJUVCJThCJUI5JUVBJUI3JUJDLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OiAyMzRweDsgd2lkdGg6IDM1MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDQgXHVhYzFjXHViYzFjXHVkNTU4XHViMjkwXHViNzdjIFx1YzVkMFx1YjEwOFx1YzljMFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMThjXHViYWE4XHVkNTc0IFx1YmM4NFx1YjliMCBcdWM1ZDBcdWI5YWRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCAkSyRcdWNkMDggXHVkNTBjXHViODA4XHVjNzc0XHVkNTVjIFx1ZDZjNCBcdWIyZjlcdWFkZmNcdWM3NDQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWFlNGNcdWM5YzAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4kLCAkSyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTiRcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJEFfaSQsICRCX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzVkMFx1YjlhZFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgJEskXHVjZDA4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1YyBcdWQ2YzQgXHVjZDVjXHViMzAwXHViODVjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZjlcdWFkZmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlIE4sS1xcbGUgMTAwJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgQV9pLEJfaVxcbGUgNTAkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRLIFxcbGUgMiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGUgNDskICRLIFxcbGUgMTAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiA9IDEkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTQzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhcnJvdCBDbGljayBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Cb3JlZCBkdXJpbmcgdGhlIHZhY2F0aW9uLCBFcmljIGRlY2lkZWQgdG8gZGV2ZWxvcCBhbmQgcGxheSBhIGdhbWUuIFRoZSBnYW1lIGlzIGNhbGxlZCA8c3Ryb25nPkNhcnJvdCBDbGljayBHYW1lPFwvc3Ryb25nPiwmbmJzcDthbmQgdGhlIHJ1bGVzIGFyZSBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIGdhbWUsIEVyaWMgaW5pdGlhbGx5IHN0YXJ0cyB0aGUgZ2FtZSB3aXRoICQwJCBjYXJyb3RzIGFuZCAkcyQgZXF1YWwgdG8gJDEkLjxcL3A+XHJcblxyXG48cD5UaGVuLCBldmVyeSBzZWNvbmQsIGhlIGNhbiB0YWtlIG9uZSBvZiB0d28gYWN0aW9uczxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkNsaWNrJm5ic3A7YW5kIGdldCAkcyQgY2Fycm90cy48XC9saT5cclxuXHQ8bGk+Q2hvb3NlIGFuIGludGVnZXIgJGkkJCgxIFxcbGUgaSBcXGxlIE4pJC4gVGhlbiwgcGF5ICRBX2kkIG9mIHRoZSBjYXJyb3RzIHlvdSBoYXZlJm5ic3A7YW5kIGJ1eSB0aGUgJGkkLXRoIHNwZWVkIGVmZmVjdC4mbmJzcDtJbiB0aGlzIGNhc2UsICRzJCBpcyBpbmNyZWFzZWQgYnkgJEJfaSQuIChZb3UgY2FuIGFsc28gYnV5IGFnYWluIGEgcHJldmlvdXNseSBib3VnaHQgc3BlZWQgZWZmZWN0KS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91LmFjbWljcGMubmV0XC8wNjc0MTQ2YS1jNGNhLTQxYjEtYjk4NC1kMDNkMTM1ZWM0NGZcLyVFQiU4QiVCOSVFQSVCNyVCQyVFQiU4QiVCOSVFQSVCNyVCQy5wbmdcIiBzdHlsZT1cImhlaWdodDogMjM0cHg7IHdpZHRoOiAzNTBweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+TGV0JiMzOTtzIGhlbHAgRXJpYywgd2hvIGhhcyBleGhhdXN0ZWQgYWxsIGhpcyBlbmVyZ3kgZGV2ZWxvcGluZyB0aGUgZ2FtZSwgYnkgZmluZGluZyBvdXQgaG93IG1hbnkgY2Fycm90cyBoZSBjYW4gb2J0YWluIGFmdGVyIHBsYXlpbmcgdGhlIGdhbWUgZm9yICRLJCBzZWNvbmRzITxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkTiQgYW5kICRLJC48XC9wPlxyXG5cclxuPHA+VGhlICRpJC10aCBsaW5lIG9mIHRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEFfaSQgYW5kICRCX2kkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXJyb3RzIHRoYXQgY2FuIGJlIG9idGFpbmVkIGFmdGVyIHBsYXlpbmcgdGhlIGdhbWUgZm9yICRLJCBzZWNvbmRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlIE4sS1xcbGUgMTAwJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgQV9pLEJfaVxcbGUgNTAkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRLIFxcbGUgMiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGUgNDskJm5ic3A7JEsgXFxsZSAxMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROID0gMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHM8XC9wPlxyXG4ifV0=