문제
리듬게이머 코더빡은 최근 댄스 댄스 레볼루션(DDR)에 푹 빠져있다. 이 게임은 곡이 재생될 때 떨어지는 노트에 맞춰 발판을 밟는 게임으로, 많은 체력을 소모하기 때문에 체력 관리가 매우 중요하다.
곡은 $N$개의 구간으로 이루어져 있고, 어떠한 구간 $i$ $(1 \le i \le N)$에 대해 코더빡은 해당 구간을 플레이할지, 포기할지 선택할 수 있다. 해당 구간을 플레이할 때 얻을 수 있는 점수는 $s_i$점이며, 체력을 $h_i$만큼 소모한다. 구간을 포기할 때는, 점수를 얻지 못하고 체력도 소모하지 않는다.
곡이 시작할 때, 코더빡은 체력 100ドル$을 가지고 시작한다. 매 구간에 진입하기 전에 체력을 $K$만큼 회복한다. 이 체력 회복은 구간을 플레이하거나 포기하는 것과는 무관하게 일어남에 유의하라. 회복 후 코더빡의 체력이 100ドル$을 초과하는 경우 체력이 100ドル$이 되며, 구간을 플레이했을 때 체력이 0ドル$ 미만으로 하락하는 경우 코더빡은 해당 구간을 포기해야만 한다.
하루 종일 DDR을 밟아 기진맥진인 코더빡은 더 이상 체력 관리를 위한 판단을 내릴 수 없다. 코더빡이 성과를 뽑아낼 수 있도록 그가 얻을 수 있는 최대 점수를 알려주는 프로그램을 작성하시오.
지문에서 언급하지 않은 게임오버 등의 시스템은 이 문제에서 고려하지 않는다.
출력
코더빡이 얻을 수 있는 최대 점수를 출력한다.
세 구간 이상을 플레이하는 방법은 없다. 90ドル$점짜리 구간을 플레이한 후 체력이 40ドル$이 되며, 1ドル$개의 구간을 포기하고 체력을 2ドル$번 회복해 100ドル$점짜리 구간을 플레이하는 방법으로 최대 점수인 190ドル$점을 얻을 수 있다.
W3sicHJvYmxlbV9pZCI6IjI5NzU2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiRERSIFx1Y2NiNFx1YjgyNSBcdWFkMDBcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjlhY1x1YjRlY1x1YWM4Y1x1Yzc3NFx1YmEzOCBcdWNmNTRcdWIzNTRcdWJlNjFcdWM3NDAgXHVjZDVjXHVhZGZjIFx1YjMwNFx1YzJhNCBcdWIzMDRcdWMyYTQgXHViODA4XHViY2ZjXHViOGU4XHVjMTU4KEREUilcdWM1ZDAgXHVkNDc5IFx1YmU2MFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWFjZTFcdWM3NzQgXHVjN2FjXHVjMGRkXHViNDIwIFx1YjU0YyBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHViMTc4XHVkMmI4XHVjNWQwIFx1YjlkZVx1Y2RiMCBcdWJjMWNcdWQzMTBcdWM3NDQgXHViYzFmXHViMjk0IFx1YWM4Y1x1Yzc4NFx1YzczY1x1Yjg1YywgXHViOWNlXHVjNzQwIFx1Y2NiNFx1YjgyNVx1Yzc0NCBcdWMxOGNcdWJhYThcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2NiNFx1YjgyNSBcdWFkMDBcdWI5YWNcdWFjMDAgXHViOWU0XHVjNmIwIFx1YzkxMVx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UxXHVjNzQwICROJFx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNWI0XHViNWEwXHVkNTVjIFx1YWQ2Y1x1YWMwNCAkaSQgJCgxIFxcbGUgaSBcXGxlIE4pJFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZjU0XHViMzU0XHViZTYxXHVjNzQwIFx1ZDU3NFx1YjJmOSBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTYwXHVjOWMwLCBcdWQzZWNcdWFlMzBcdWQ1NjBcdWM5YzAgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU3NFx1YjJmOSBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTYwIFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWIyOTQgJHNfaSRcdWM4MTBcdWM3NzRcdWJhNzAsIFx1Y2NiNFx1YjgyNVx1Yzc0NCAkaF9pJFx1YjljY1x1ZDA3YyBcdWMxOGNcdWJhYThcdWQ1NWNcdWIyZTQuIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWQzZWNcdWFlMzBcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWNlMCBcdWNjYjRcdWI4MjVcdWIzYzQgXHVjMThjXHViYWE4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UxXHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWI1NGMsIFx1Y2Y1NFx1YjM1NFx1YmU2MVx1Yzc0MCBcdWNjYjRcdWI4MjUgJDEwMCRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViOWU0IFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWM5YzRcdWM3ODVcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1Y2NiNFx1YjgyNVx1Yzc0NCAkSyRcdWI5Y2NcdWQwN2MgXHVkNjhjXHViY2Y1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjY2I0XHViODI1IFx1ZDY4Y1x1YmNmNVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTU4XHVhYzcwXHViMDk4IFx1ZDNlY1x1YWUzMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWFjZmNcdWIyOTQgXHViYjM0XHVhZDAwXHVkNTU4XHVhYzhjIFx1Yzc3Y1x1YzViNFx1YjBhOFx1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWI3N2MuIFx1ZDY4Y1x1YmNmNSBcdWQ2YzQgXHVjZjU0XHViMzU0XHViZTYxXHVjNzU4IFx1Y2NiNFx1YjgyNVx1Yzc3NCAkMTAwJFx1Yzc0NCBcdWNkMDhcdWFjZmNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwIFx1Y2NiNFx1YjgyNVx1Yzc3NCAkMTAwJFx1Yzc3NCBcdWI0MThcdWJhNzAsIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1ODhcdWM3NDQgXHViNTRjIFx1Y2NiNFx1YjgyNVx1Yzc3NCAkMCQgXHViYmY4XHViOWNjXHVjNzNjXHViODVjIFx1ZDU1OFx1Yjc3ZFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVjZjU0XHViMzU0XHViZTYxXHVjNzQwIFx1ZDU3NFx1YjJmOSBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkM2VjXHVhZTMwXHVkNTc0XHVjNTdjXHViOWNjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViOGU4IFx1Yzg4NVx1Yzc3YyBERFJcdWM3NDQgXHViYzFmXHVjNTQ0IFx1YWUzMFx1YzljNFx1YjllNVx1YzljNFx1Yzc3OCBcdWNmNTRcdWIzNTRcdWJlNjFcdWM3NDAgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWNjYjRcdWI4MjUgXHVhZDAwXHViOWFjXHViOTdjIFx1YzcwNFx1ZDU1YyBcdWQzMTBcdWIyZThcdWM3NDQgXHViMGI0XHViOWI0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Y2Y1NFx1YjM1NFx1YmU2MVx1Yzc3NCBcdWMxMzFcdWFjZmNcdWI5N2MgXHViZjUxXHVjNTQ0XHViMGJjIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVhZGY4XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNTRjXHViODI0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YmIzOFx1YzVkMFx1YzExYyBcdWM1YjhcdWFlMDlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWM4Y1x1Yzc4NFx1YzYyNFx1YmM4NCBcdWI0ZjFcdWM3NTggXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQwIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4kXHVhY2ZjICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJE4kXHVjNzQwIFx1YWNlMVx1Yzc1OCBcdWM4MDRcdWNjYjQgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWJhNzAsICRLJFx1YjI5NCBcdWQ2OGNcdWJjZjVcdWQ1NThcdWIyOTQgXHVjY2I0XHViODI1XHVjNzU4IFx1YzU5MVx1Yzc3NFx1YjJlNC4gJCgxIFxcbGVxIE4gXFxsZXEgMVxcLDAwMDskICQxIFxcbGVxIEsgXFxsZXEgMTApJDxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggJHNfMSQsICRzXzIkLCAkXFxjZG90cyQsICRzX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgc19pIFxcbGVxIDFcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggJGhfMSQsICRoXzIkLCAkXFxjZG90cyQsICRoX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgaF9pIFxcbGVxIDEwMCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZjU0XHViMzU0XHViZTYxXHVjNzc0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWJhYThcdWI0ZTAgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5cdWMxMzggXHVhZDZjXHVhYzA0IFx1Yzc3NFx1YzBjMVx1Yzc0NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzVjNlx1YjJlNC4gJDkwJFx1YzgxMFx1YzlkY1x1YjlhYyBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTVjIFx1ZDZjNCBcdWNjYjRcdWI4MjVcdWM3NzQgJDQwJFx1Yzc3NCBcdWI0MThcdWJhNzAsICQxJFx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkM2VjXHVhZTMwXHVkNTU4XHVhY2UwIFx1Y2NiNFx1YjgyNVx1Yzc0NCAkMiRcdWJjODggXHVkNjhjXHViY2Y1XHVkNTc0ICQxMDAkXHVjODEwXHVjOWRjXHViOWFjIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWM3NzgmbmJzcDskMTkwJFx1YzgxMFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyOTc1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkREUiBTdGFtaW5hIE1hbmFnZW1lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPktvZGVycGFyaywgYSByaHl0aG0gZ2FtZXIsIGlzIGN1cnJlbnRseSBlbmdyb3NzZWQgaW4gRGFuY2UgRGFuY2UgUmV2b2x1dGlvbiAoRERSKS4gUGxheWVycyBzdGVwIG9uIHRoZSBwYW5lbHMgaW4gdGltZSB3aXRoIHRoZSBmYWxsaW5nIGFycm93cyBpbiB0aGlzIGdhbWUuIFNpbmNlIGl0IHJlcXVpcmVzIGEgc2lnbmlmaWNhbnQgYW1vdW50IG9mIHN0YW1pbmEsIG1hbmFnaW5nIHN0YW1pbmEgaXMgY3J1Y2lhbC48XC9wPlxyXG5cclxuPHA+QSBzb25nIGNvbnNpc3RzIG9mICROJCBzZWN0aW9ucywgYW5kIGZvciBhbnkgZ2l2ZW4gc2VjdGlvbiAkaSQgKHdoZXJlICQxIFxcbGUgaSZuYnNwO1xcbGUgTiQpLCBLb2RlcnBhcmsgY2FuIGNob29zZSB0byBwbGF5IG9yIHNraXAgdGhhdCBzZWN0aW9uLiBXaGVuIGhlIGRlY2lkZXMgdG8gcGxheSBhIHNlY3Rpb24sIGhlIGNhbiBlYXJuICRzX2kkXHUyMDBiIHBvaW50cyBidXQgd2lsbCBhbHNvIGNvbnN1bWUgJGhfaSRcdTIwMGIgc3RhbWluYS4gSWYgaGUgc2tpcHMgYSBzZWN0aW9uLCBoZSBkb2VzbiYjMzk7dCBlYXJuIGFueSBwb2ludHMgYW5kIGRvZXNuJiMzOTt0IGNvbnN1bWUgYW55IHN0YW1pbmEuPFwvcD5cclxuXHJcbjxwPkF0IHRoZSBzdGFydCBvZiBhIHNvbmcsIEtvZGVycGFyayBiZWdpbnMgd2l0aCAkMTAwJCBzdGFtaW5hLiBCZWZvcmUgZW50ZXJpbmcgZWFjaCBzZWN0aW9uLCBoZSByZWNvdmVycyAkSyQgc3RhbWluYS4gVGhpcyBzdGFtaW5hIHJlY292ZXJ5IGhhcHBlbnMgcmVnYXJkbGVzcyBvZiB3aGV0aGVyIEtvZGVycGFyayBwbGF5cyBvciBza2lwcyB0aGUgc2VjdGlvbi4gQWZ0ZXIgcmVjb3ZlcnksIGlmIEtvZGVycGFyayYjMzk7cyBzdGFtaW5hIGV4Y2VlZHMgJDEwMCQsJm5ic3A7aXQmIzM5O3MgcmVzZXQgdG8gJDEwMCQuIElmLCBhZnRlciBwbGF5aW5nIGEgc2VjdGlvbiwgaGlzIHN0YW1pbmEgZHJvcHMgYmVsb3cgJDAkLCBoZSBtdXN0IHNraXAgdGhhdCBzZWN0aW9uLjxcL3A+XHJcblxyXG48cD5IYXZpbmcgcGxheWVkIEREUiBhbGwgZGF5IGFuZCB1dHRlcmx5IGV4aGF1c3RlZCwgS29kZXJwYXJrIGNhbiBubyBsb25nZXIgZGVjaWRlIGhvdyB0byBtYW5hZ2UgaGlzIHN0YW1pbmEuIFdyaXRlIGEgcHJvZ3JhbSB0byBnZXQgdGhlIG1heGltdW0gc2NvcmUgS29kZXJwYXJrIGNhbiBhY2hpZXZlLjxcL3A+XHJcblxyXG48cD5TeXN0ZW1zIG5vdCBtZW50aW9uZWQgaW4gdGhlIGRlc2NyaXB0aW9uLCBsaWtlICZxdW90O2dhbWUgb3ZlciwmcXVvdDsgYXJlIG5vdCBjb25zaWRlcmVkIGluIHRoaXMgcHJvYmxlbS48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsIHRoZSB0b3RhbCBudW1iZXIgb2Ygc2VjdGlvbnMgaW4gdGhlIHNvbmcgJE4kIGFuZCB0aGUgYW1vdW50IG9mIHN0YW1pbmEgcmVjb3ZlcmVkICRLJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMSBcXGxlcSBOIFxcbGVxIDFcXCwwMDA7JCAkMSBcXGxlcSBLIFxcbGVxIDEwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zJm5ic3A7dGhlIGludGVnZXJzJm5ic3A7JHNfMSQsICRzXzIkLCAkXFxjZG90cyQsICRzX04kXHUyMDBiLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDEgXFxsZXEgc19pJm5ic3A7XFxsZXEgMVxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyAkaF8xJCwgJGhfMiQsICRcXGNkb3RzJCwgJGhfTiQsIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMSBcXGxlcSBoX2kmbmJzcDtcXGxlcSAxMDApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtYXhpbXVtIHNjb3JlIEtvZGVycGFyayBjYW4gYWNoaWV2ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkhlIGNhbiBwbGF5IGFsbCB0aGUgc2VjdGlvbnMuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlRoZXJlIGlzIG5vIG1ldGhvZCB0byBwbGF5IG1vcmUgdGhhbiB0d28gc2VjdGlvbnMuIEFmdGVyIHBsYXlpbmcgdGhlICQ5MCQtcG9pbnQgc2VjdGlvbiwgdGhlIHN0YW1pbmEgYmVjb21lcyAkNDAkLiBCeSBza2lwcGluZyBvbmUgc2VjdGlvbiBhbmQgcmVjb3ZlcmluZyBzdGFtaW5hIHR3aWNlLCBLb2RlcnBhcmsgY2FuIHRoZW4gcGxheSB0aGUgJDEwMCQtcG9pbnQgc2VjdGlvbiwgYWNoaWV2aW5nIGEgbWF4aW11bSBzY29yZSBvZiAkMTkwJCBwb2ludHMuPFwvcD5cclxuIn1d