문제
메이플 스토리에는 블레싱 마하, 하울링같이 자신의 공격력을 변화시키는 버프 스킬이 있다. 메이플을 즐겨하는 20년차 고인물 임스는 공격 스킬만 쓰는 메이플에 질려 위의 예시와 같은 버프 스킬을 이용하여 자기만의 독특한 방식으로 보스를 잡아보려고 한다.
임스는 $N$개의 버프 스킬이 있는데, $i$번째 스킬은 공격력을 $a_{i}$ 배로 증가시키고 $b_{i}$ 만큼 더하는 스킬이다. 이때, $b_{i}$가 음수일 수도 있다. 만약 $a_{i} = 3,ドル $b_{i} = 5$이고 현재 공격력이 $x$라면, $i$번 스킬을 사용한 이후에 공격력이 $x\times3+5$로 변경된다. 스킬은 여러 번 사용이 가능하며, 사용한 순서대로 적용된다.
임스는 오늘도 $Q$개의 던전을 깨려고 한다. 각 던전에는 보스가 존재하는데, 보스마다 체력이 다르다. 또한, 보스마다 레벨과 방어율 등이 달라 임스의 초기 공격력은 임스가 상대하는 보스에 따라 다르다.
임스의 공격력이 보스의 체력과 같거나 높아지면 보스를 한 대에 잡을 수 있다. 이때, 단 한 대에 보스를 잡기 위해선 최소 몇 번의 스킬을 사용해야 할까?
출력
각각의 던전마다 보스를 한 대에 잡기 위해 사용해야 하는 최소 스킬 사용 횟수를 한 줄에 하나씩 출력한다.
주어진 스킬로 보스를 한 대에 잡을 수 없는 경우 -1을 출력한다.
W3sicHJvYmxlbV9pZCI6IjI5Nzk1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTVjIFx1YjMwMCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8yMjI4ZjY1MS0yYWI2LTRiY2YtOGM1YS1hOTA4MzUwMWJkMzhcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJhNTRcdWM3NzRcdWQ1MGMgXHVjMmE0XHVkMWEwXHViOWFjXHVjNWQwXHViMjk0IFx1YmUxNFx1YjgwOFx1YzJmMSBcdWI5YzhcdWQ1NTgsIFx1ZDU1OFx1YzZiOFx1YjljMVx1YWMxOVx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVhY2Y1XHVhY2E5XHViODI1XHVjNzQ0IFx1YmNjMFx1ZDY1NFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWJjODRcdWQ1MDQgXHVjMmE0XHVkMGFjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYTU0XHVjNzc0XHVkNTBjXHVjNzQ0IFx1Yzk5MFx1YWNhOFx1ZDU1OFx1YjI5NCAyMFx1YjE0NFx1Y2MyOCBcdWFjZTBcdWM3NzhcdWJiM2MgXHVjNzg0XHVjMmE0XHViMjk0IFx1YWNmNVx1YWNhOSBcdWMyYTRcdWQwYWNcdWI5Y2MgXHVjNGYwXHViMjk0IFx1YmE1NFx1Yzc3NFx1ZDUwY1x1YzVkMCBcdWM5YzhcdWI4MjQgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzJkY1x1YzY0MCBcdWFjMTlcdWM3NDAgXHViYzg0XHVkNTA0IFx1YzJhNFx1ZDBhY1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNzkwXHVhZTMwXHViOWNjXHVjNzU4IFx1YjNjNVx1ZDJiOVx1ZDU1YyBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHViY2Y0XHVjMmE0XHViOTdjIFx1YzdhMVx1YzU0NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NFx1YzJhNFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHViYzg0XHVkNTA0IFx1YzJhNFx1ZDBhY1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsICRpJFx1YmM4OFx1YzlmOCBcdWMyYTRcdWQwYWNcdWM3NDAgXHVhY2Y1XHVhY2E5XHViODI1XHVjNzQ0ICRhX3tpfSQgXHViYzMwXHViODVjIFx1Yzk5ZFx1YWMwMFx1YzJkY1x1ZDBhNFx1YWNlMCAkYl97aX0kIFx1YjljY1x1ZDA3YyBcdWIzNTRcdWQ1NThcdWIyOTQgXHVjMmE0XHVkMGFjXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsICRiX3tpfSRcdWFjMDAgXHVjNzRjXHVjMjE4XHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCAkYV97aX0gPSAzJCwgJGJfe2l9ID0gNSRcdWM3NzRcdWFjZTAgXHVkNjA0XHVjN2FjIFx1YWNmNVx1YWNhOVx1YjgyNVx1Yzc3NCAkeCRcdWI3N2NcdWJhNzQsICRpJFx1YmM4OCBcdWMyYTRcdWQwYWNcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjIFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWFjZjVcdWFjYTlcdWI4MjVcdWM3NzQgJHhcXHRpbWVzMys1JFx1Yjg1YyBcdWJjYzBcdWFjYmRcdWI0MWNcdWIyZTQuIFx1YzJhNFx1ZDBhY1x1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzAsIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODRcdWMyYTRcdWIyOTQgXHVjNjI0XHViMjk4XHViM2M0ICRRJFx1YWMxY1x1Yzc1OCBcdWIzNThcdWM4MDRcdWM3NDQgXHVhZTY4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YjM1OFx1YzgwNFx1YzVkMFx1YjI5NCBcdWJjZjRcdWMyYTRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWJjZjRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2I0XHViODI1XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWJjZjRcdWMyYTRcdWI5YzhcdWIyZTQgXHViODA4XHViY2E4XHVhY2ZjIFx1YmMyOVx1YzViNFx1YzcyOCBcdWI0ZjFcdWM3NzQgXHViMmVjXHViNzdjIFx1Yzc4NFx1YzJhNFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVhY2Y1XHVhY2E5XHViODI1XHVjNzQwIFx1Yzc4NFx1YzJhNFx1YWMwMCBcdWMwYzFcdWIzMDBcdWQ1NThcdWIyOTQgXHViY2Y0XHVjMmE0XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NFx1YzJhNFx1Yzc1OCBcdWFjZjVcdWFjYTlcdWI4MjVcdWM3NzQgXHViY2Y0XHVjMmE0XHVjNzU4IFx1Y2NiNFx1YjgyNVx1YWNmYyBcdWFjMTlcdWFjNzBcdWIwOTggXHViMTkyXHVjNTQ0XHVjOWMwXHViYTc0IFx1YmNmNFx1YzJhNFx1Yjk3YyBcdWQ1NWMgXHViMzAwXHVjNWQwIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjJlOCBcdWQ1NWMgXHViMzAwXHVjNWQwIFx1YmNmNFx1YzJhNFx1Yjk3YyBcdWM3YTFcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTIwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4XHVjNzU4IFx1YzJhNFx1ZDBhY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTYwXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyYTRcdWQwYWNcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWIzNThcdWM4MDRcdWM3NTggXHVjMjE4ICRRJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgTixRIFxcbGUgMzAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwICRpJFx1YmM4OCBcdWMyYTRcdWQwYWNcdWM3NTggXHVjODE1XHViY2Y0XHVjNzc4ICRhX3tpfSQsICRiX3tpfSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIGFfe2l9IFxcbGUgMVxcLDAwMFxcLDAwMDsgLTEwXns5fSBcXGxlIGJfe2l9IFxcbGUgMTBeezl9KSQ8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4XHVjOWY4IFx1YjM1OFx1YzgwNFx1YzVkMFx1YzExYyBcdWNkMDhcdWFlMzAgXHVhY2Y1XHVhY2E5XHViODI1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAkeF97aX0kXHVjNjQwIFx1YjM1OFx1YzgwNCBcdWJjZjRcdWMyYTRcdWM3NTggXHVjY2I0XHViODI1ICR5X3tpfSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSB4X3tpfSwgeV97aX0gXFxsZSAxMF57MTJ9KSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHViMzU4XHVjODA0XHViOWM4XHViMmU0IFx1YmNmNFx1YzJhNFx1Yjk3YyBcdWQ1NWMgXHViMzAwXHVjNWQwIFx1YzdhMVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmE0XHVkMGFjIFx1YzBhY1x1YzZhOSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMmE0XHVkMGFjXHViODVjIFx1YmNmNFx1YzJhNFx1Yjk3YyBcdWQ1NWMgXHViMzAwXHVjNWQwIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+LTE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTc5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9uZS1IaXQgS2lsbCIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lN2M1MDdmNC1iMTRhLTRiMTctYTYzOC0xM2Y5NWYxODZkNDFcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48cD5JbiA8ZW0+TWFwbGVTdG9yeTxcL2VtPiwgdGhlcmUgYXJlIGJ1ZmYgc2tpbGxzIGxpa2UgPGVtPk1haGEgQmxlc3Npbmc8XC9lbT4mbmJzcDthbmQgPGVtPkNhbGwgb2YgdGhlIFdpbGQ8XC9lbT4gdGhhdCBjaGFuZ2UgeW91ciBhdHRhY2sgcG93ZXIuIGxtczA4MDYsIGEgMjAteWVhciB2ZXRlcmFuIG9mIDxlbT5NYXBsZVN0b3J5PFwvZW0+LCBpcyB0aXJlZCBvZiB1c2luZyBvbmx5IGF0dGFjayBza2lsbHMuIEhlJm5ic3A7cGxhbnMgdG8gZGVmZWF0IGJvc3NlcyBpbiBhIHVuaXF1ZSB3YXkgdXNpbmcgc3VjaCBidWZmIHNraWxscy48XC9wPlxyXG5cclxuPHA+bG1zMDgwNiBoYXMgJE4kIGRpZmZlcmVudCBidWZmIHNraWxscy4gVGhlICRpXlxcdGV4dHt0aH0kIHNraWxsIGluY3JlYXNlcyB0aGUgYXR0YWNrIHBvd2VyIGJ5IGEgZmFjdG9yIG9mICRhX2kkXHUyMDBiIGFuZCB0aGVuIGFkZHMgJGJfaSRcdTIwMGIgdG8gaXQuIE5vdGUgdGhhdCAkYl9pJFx1MjAwYiBjYW4gYWxzbyBiZSBuZWdhdGl2ZS4gSWYgJGFfe2l9Jm5ic3A7PSAzJCBhbmQmbmJzcDskYl97aX0gPSA1JCwgYW5kIHRoZSBjdXJyZW50IGF0dGFjayBwb3dlciBpcyAkeCQsIHRoZW4gYWZ0ZXIgdXNpbmcgdGhlICRpXlxcdGV4dHt0aH0kIHNraWxsLCB0aGUgYXR0YWNrIHBvd2VyIGJlY29tZXMgJHhcXHRpbWVzMys1JC4gU2tpbGxzIGNhbiBiZSB1c2VkIG11bHRpcGxlIHRpbWVzIGFuZCBhcmUgYXBwbGllZCBpbiB0aGUgb3JkZXIgdXNlZC48XC9wPlxyXG5cclxuPHA+bG1zMDgwNiBwbGFucyB0byBjbGVhciAkUSQgZHVuZ2VvbnMgdG9kYXkuIEVhY2ggZHVuZ2VvbiBoYXMgYSBib3NzIHdpdGggdmFyeWluZyBIUHMuIEFkZGl0aW9uYWxseSwgdGhlIGJvc3NlcyBoYXZlIGRpZmZlcmVudCBsZXZlbHMgYW5kIGRlZmVuc2UgcmF0ZXMsIHNvIGxtczA4MDYmIzM5O3MgaW5pdGlhbCBhdHRhY2sgcG93ZXIgdmFyaWVzIGRlcGVuZGluZyBvbiB0aGUgYm9zcyBoZSBpcyBmYWNpbmcuPFwvcD5cclxuXHJcbjxwPklmIGxtczA4MDYmIzM5O3MmbmJzcDthdHRhY2sgcG93ZXIgZXF1YWxzIG9yIGV4Y2VlZHMgdGhlIGJvc3MmIzM5O3MgSFAsIGhlIGNhbiBkZWZlYXQgdGhlIGJvc3MgaW4gb25lIGhpdC4gSW4gdGhpcyBjYXNlLCB3aGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBza2lsbHMgdGhhdCBtdXN0IGJlIHVzZWQgdG8gZGVmZWF0IHRoZSBib3NzIGluIGEgc2luZ2xlIGhpdD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyZuYnNwO3JlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHNraWxscyAkTiQgYW5kIHRoZSBudW1iZXIgb2YgZHVuZ2VvbnMgJFEkLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxIFxcbGUgTixRIFxcbGUgMzAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyZuYnNwOyROJCBsaW5lcyBjb250YWluJm5ic3A7dHdvIGludGVnZXJzIGZvciBlYWNoIGxpbmUsIHByb3ZpZGluZyZuYnNwO3RoZSBkZXRhaWxzIG9mIGVhY2ggc2tpbGwgJGFfe2l9JCBhbmQmbmJzcDskYl97aX0kLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4mbmJzcDskKDEgXFxsZSBhX3tpfSZuYnNwO1xcbGUgMVxcLDAwMFxcLDAwMCwmbmJzcDstMVxcLDAwMFxcLDAwMFxcLDAwMCZuYnNwO1xcbGUgYl97aX0gXFxsZSAxXFwsMDAwXFwsMDAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyAkUSQgbGluZXMgY29udGFpbiZuYnNwO3R3byBpbnRlZ2VycyBmb3IgZWFjaCBsaW5lLCBwcm92aWRpbmcmbmJzcDt0aGUmbmJzcDtpbml0aWFsIGF0dGFjayBwb3dlciAkeF9pJFx1MjAwYiBhbmQgdGhlIEhQIG9mIHRoZSBkdW5nZW9uIGJvc3MgJHlfaSRcdTIwMGIgZm9yIHRoZSAkaV5cXHRleHR7dGh9JCBkdW5nZW9uLiAkKDEgXFxsZSB4X3tpfSwgeV97aX0mbmJzcDtcXGxlIDEwXnsxMn0pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGR1bmdlb24sIG91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc2tpbGxzIG5lZWRlZCB0byBkZWZlYXQgdGhlIGJvc3MgaW4gb25lIGhpdCBvbiBhIG5ldyBsaW5lLjxcL3A+XHJcblxyXG48cD5JZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGRlZmVhdCB0aGUgYm9zcyBpbiBhIHNpbmdsZSBoaXQgd2l0aCB0aGUgZ2l2ZW4gc2tpbGxzLCBvdXRwdXQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPiZuYnNwO2luc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==