문제
유민이의 쿠키 공장에 $N$개의 회사로부터 수주가 들어왔다. $i$번째 회사에는 총 $c_i$박스의 쿠키를 공급해야 하며, $s_i$일차부터 쿠키 납품을 시작할 수 있다.
공장에서는 $x$일차에 다음 두 행동 중 하나를 선택한다.
$s_i\leq x$를 만족하는 $i$를 선택한 후, 1ドル$박스의 쿠키를 만들어서 $i$번째 회사에 공급한다.
쿠키고 뭐고 사내 리듬게임 대회나 개최한다.
쿠키를 미리 만들어서 다른 날에 공급할 수 없고, 만든 쿠키는 반드시 당일 에 공급해야 함에 유의하라. 모든 회사에 쿠키 납품을 완료하기 위해 마지막으로 쿠키를 만드는 것은 최소 몇 일차가 되는지를 계산해 주자.
또한, 쿠키 산업은 워낙 한 치 앞도 내다볼 수 없기 때문에 $Q$건의 수주 조건 수정 요청이 들어왔다. $j$번째 수정 요청에서는 $q_j$번째 회사에 공급할 쿠키를 $c'_j$박스로, 공급 시작 일차를 $s'_j$일차로 수정한다. 각 수정 요청은 이후의 수정 요청들을 처리할 때도 초기화되지 않고 영향을 미침 에 유의하라. 시작 상태와 각 수정 요청 이후 에 대해 문제를 해결해 보자.
출력
첫 번째 줄에 시작 상태 에서의 문제의 정답을 출력한다.
다음 $Q$개의 줄 중 $j$번째 줄에 $j$번째 수정 요청을 처리한 후의 문제의 정답을 출력한다.
제한
1ドル\leq N,Q\leq 2\times 10^5$
1ドル\leq q_j\leq N$
1ドル\leq c_i,s_i,c'_j,s'_j\leq 10^9$
서브태스크 번호 배점 제한 1 7 $N, Q \leq 2500$
2 54 $s_i$는 수정되지 않음. 즉, 항상 $s_i = s'_{q_j}$
3 39 추가 제약 조건 없음
예제 출력 2
복사
118
20
16
14
21
20
노트
수정 요청 전후의 상태가 같을 수도 있음에 유의하라. 즉, $c'_j=c_{q_j};$ $s'_j=s_{q_j}$일 수도 있다.
W3sicHJvYmxlbV9pZCI6IjMzNDkwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZmUwXHVkMGE0IFx1YWNmNVx1YzdhNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzIwXHViYmZjXHVjNzc0XHVjNzU4IFx1Y2ZlMFx1ZDBhNCBcdWFjZjVcdWM3YTVcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1ZDY4Y1x1YzBhY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWMyMThcdWM4ZmNcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjU0XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVkNjhjXHVjMGFjXHVjNWQwXHViMjk0IFx1Y2QxZCAkY19pJFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWNmZTBcdWQwYTRcdWI5N2MgXHVhY2Y1XHVhZTA5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgJHNfaSRcdWM3N2NcdWNjMjhcdWJkODBcdWQxMzAgXHVjZmUwXHVkMGE0IFx1YjBhOVx1ZDQ4OFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2Y1XHVjN2E1XHVjNWQwXHVjMTFjXHViMjk0ICR4JFx1Yzc3Y1x1Y2MyOFx1YzVkMCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1ZDU4OVx1YjNkOSBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kc19pXFxsZXEgeCRcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0ICRpJFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVkNmM0LCAkMSRcdWJjMTVcdWMyYTRcdWM3NTggXHVjZmUwXHVkMGE0XHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzExYyAkaSRcdWJjODhcdWM5ZjggXHVkNjhjXHVjMGFjXHVjNWQwIFx1YWNmNVx1YWUwOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjZmUwXHVkMGE0XHVhY2UwIFx1YmI1MFx1YWNlMCBcdWMwYWNcdWIwYjQgXHViOWFjXHViNGVjXHVhYzhjXHVjNzg0IFx1YjMwMFx1ZDY4Y1x1YjA5OCBcdWFjMWNcdWNkNWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjZmUwXHVkMGE0XHViOTdjIFx1YmJmOFx1YjlhYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWMxMWMgXHViMmU0XHViOTc4IFx1YjBhMFx1YzVkMCBcdWFjZjVcdWFlMDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHViOWNjXHViNGUwIFx1Y2ZlMFx1ZDBhNFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgPHN0cm9uZz5cdWIyZjlcdWM3N2M8XC9zdHJvbmc+XHVjNWQwIFx1YWNmNVx1YWUwOVx1ZDU3NFx1YzU3YyBcdWQ1NjhcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLiBcdWJhYThcdWI0ZTAgXHVkNjhjXHVjMGFjXHVjNWQwIFx1Y2ZlMFx1ZDBhNCBcdWIwYTlcdWQ0ODhcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjZmUwXHVkMGE0XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NDAgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWM3N2NcdWNjMjhcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NCBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVjZmUwXHVkMGE0IFx1YzBiMFx1YzVjNVx1Yzc0MCBcdWM2Y2NcdWIwOTkgXHVkNTVjIFx1Y2U1OCBcdWM1NWVcdWIzYzQgXHViMGI0XHViMmU0XHViY2ZjIFx1YzIxOCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwICRRJFx1YWM3NFx1Yzc1OCBcdWMyMThcdWM4ZmMgXHVjODcwXHVhYzc0IFx1YzIxOFx1YzgxNSBcdWM2OTRcdWNjYWRcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjU0XHViMmU0LiAkaiRcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1IFx1YzY5NFx1Y2NhZFx1YzVkMFx1YzExY1x1YjI5NCAkcV9qJFx1YmM4OFx1YzlmOCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVhY2Y1XHVhZTA5XHVkNTYwIFx1Y2ZlMFx1ZDBhNFx1Yjk3YyAkYyYjMzk7X2okXHViYzE1XHVjMmE0XHViODVjLCBcdWFjZjVcdWFlMDkgXHVjMmRjXHVjNzkxIFx1Yzc3Y1x1Y2MyOFx1Yjk3YyAkcyYjMzk7X2okXHVjNzdjXHVjYzI4XHViODVjIFx1YzIxOFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzIxOFx1YzgxNSBcdWM2OTRcdWNjYWRcdWM3NDAgXHVjNzc0XHVkNmM0XHVjNzU4IFx1YzIxOFx1YzgxNSBcdWM2OTRcdWNjYWRcdWI0ZTRcdWM3NDQgXHVjYzk4XHViOWFjXHVkNTYwIFx1YjU0Y1x1YjNjNCBcdWNkMDhcdWFlMzBcdWQ2NTRcdWI0MThcdWM5YzAgXHVjNTRhXHVhY2UwIDxzdHJvbmc+XHVjNjAxXHVkNWE1XHVjNzQ0IFx1YmJmOFx1Y2U2ODxcL3N0cm9uZz5cdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLiA8c3Ryb25nPlx1YzJkY1x1Yzc5MSBcdWMwYzFcdWQwZGNcdWM2NDAgXHVhYzAxIFx1YzIxOFx1YzgxNSBcdWM2OTRcdWNjYWQgXHVjNzc0XHVkNmM0PFwvc3Ryb25nPlx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICROJFx1YWMxY1x1Yzc1OCBcdWM5MDQgXHVjOTExICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJGNfaSQsICRzX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCAkUSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWM5MTEgJGokXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkcV9qJCwgJGMmIzM5O19qJCwgJHMmIzM5O19qJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCA8c3Ryb25nPlx1YzJkY1x1Yzc5MSBcdWMwYzFcdWQwZGM8XC9zdHJvbmc+XHVjNWQwXHVjMTFjXHVjNzU4IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWM5MTEgJGokXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkaiRcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1IFx1YzY5NFx1Y2NhZFx1Yzc0NCBcdWNjOThcdWI5YWNcdWQ1NWMgXHVkNmM0XHVjNzU4IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWMyMThcdWM4MTUgXHVjNjk0XHVjY2FkIFx1YzgwNFx1ZDZjNFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3NGNcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLiBcdWM5ODksICRjJiMzOTtfaj1jX3txX2p9OyQgJHMmIzM5O19qPXNfe3Ffan0kXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlcSBOLFFcXGxlcSAyXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIHFfalxcbGVxIE4kPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgY19pLHNfaSxjJiMzOTtfaixzJiMzOTtfalxcbGVxIDEwXjkkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROLCBRIFxcbGVxIDI1MDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kc19pJFx1YjI5NCBcdWMyMThcdWM4MTVcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzRjLiBcdWM5ODksIFx1ZDU2ZFx1YzBjMSAkc19pID0gcyYjMzk7X3txX2p9JDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwIFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzQgXHVjNWM2XHVjNzRjPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM0OTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb29raWUgRmFjdG9yeSIsImRlc2NyaXB0aW9uIjoiPHA+WXVtaW4mcnNxdW87cyBjb29raWUgZmFjdG9yeSBoYXMgcmVjZWl2ZWQgb3JkZXJzIGZyb20gJE4kIGNvbXBhbmllcy4gVGhlICRpJC10aCBjb21wYW55IHJlcXVpcmVzIGEgdG90YWwgb2YgJGNfaSQgYm94ZXMgb2YgY29va2llcywgYW5kIHRoZSBmYWN0b3J5IGNhbiBzdGFydCBzdXBwbHlpbmcgdGhlbSBmcm9tIGRheSAkc19pJCBvbndhcmRzLjxcL3A+XHJcblxyXG48cD5FYWNoIGRheSAkeCQsIHRoZSBmYWN0b3J5IG11c3QgY2hvb3NlIG9uZSBvZiB0aGUgZm9sbG93aW5nIHR3byBhY3Rpb25zOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlNlbGVjdCBhbiBpbmRleCAkaSQgc3VjaCB0aGF0ICRzX2lcXGxlcSB4JCwgcHJvZHVjZSBvbmUgYm94IG9mIGNvb2tpZXMsIGFuZCBkZWxpdmVyIGl0IHRvIHRoZSAkaSQtdGggY29tcGFueS48XC9saT5cclxuXHQ8bGk+Rm9yZ2V0IGFib3V0IGNvb2tpZXMgYWx0b2dldGhlciBhbmQgaG9sZCBhbiBpbi1ob3VzZSByaHl0aG0gZ2FtZSBjb21wZXRpdGlvbi48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Ob3RlIHRoYXQgY29va2llcyBjYW5ub3QgYmUgcHJvZHVjZWQgaW4gYWR2YW5jZSBmb3IgZnV0dXJlIGRlbGl2ZXJpZXM7IGFsbCBjb29raWVzIHByb2R1Y2VkIG11c3QgYmUgZGVsaXZlcmVkIG9uIDxzdHJvbmc+dGhlIHNhbWUgZGF5PFwvc3Ryb25nPi4gWW91ciB0YXNrIGlzIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBwb3NzaWJsZSBsYXN0IGRheSBvbiB3aGljaCBjb29raWUgcHJvZHVjdGlvbiBtdXN0IHRha2UgcGxhY2UgdG8gZnVsZmlsbCBhbGwgb3JkZXJzLjxcL3A+XHJcblxyXG48cD5GdXJ0aGVybW9yZSwgc2luY2UgdGhlIGNvb2tpZSBpbmR1c3RyeSBpcyBoaWdobHkgdW5wcmVkaWN0YWJsZSwgdGhlcmUgYXJlICRRJCBtb2RpZmljYXRpb24gcmVxdWVzdHMgcmVnYXJkaW5nIHRoZSBvcmRlciBjb25kaXRpb25zLiBUaGUgJGokLXRoIG1vZGlmaWNhdGlvbiByZXF1ZXN0IHVwZGF0ZXMgdGhlIG9yZGVyIG9mIHRoZSAkcV9qJC10aCBjb21wYW55LCBjaGFuZ2luZyBpdHMgcmVxdWlyZWQgbnVtYmVyIG9mIGNvb2tpZSBib3hlcyB0byAkYyYjMzk7X2okIGFuZCBpdHMgc3RhcnRpbmcgZGVsaXZlcnkgZGF5IHRvICRzJiMzOTtfaiQuIE5vdGUgdGhhdCB0aGVzZSBtb2RpZmljYXRpb25zIDxzdHJvbmc+cGVyc2lzdDxcL3N0cm9uZz4gdGhyb3VnaCBzdWJzZXF1ZW50IHJlcXVlc3RzIHJhdGhlciB0aGFuIHJlc2V0dGluZyB0aGUgb3JkZXIgY29uZGl0aW9ucyBlYWNoIHRpbWUuIFNvbHZlIHRoZSBwcm9ibGVtIGZvciBib3RoIDxzdHJvbmc+dGhlIGluaXRpYWwgc3RhdGUgYW5kIGFmdGVyIGVhY2ggbW9kaWZpY2F0aW9uIHJlcXVlc3Q8XC9zdHJvbmc+LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkTiQuPFwvcD5cclxuXHJcbjxwPlRoZSAkaSQtdGggbGluZSBvZiB0aGUgZm9sbG93aW5nICROJCBsaW5lcyBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRjX2kkIGFuZCAkc19pJC48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICRRJC48XC9wPlxyXG5cclxuPHA+VGhlICRqJC10aCBsaW5lIG9mIHRoZSBmb2xsb3dpbmcgJFEkIGxpbmVzIGNvbnRhaW5zIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkcV9qJCwgJGMmIzM5O19qJCwgYW5kICRzJiMzOTtfaiQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUsIHByaW50IHRoZSBhbnN3ZXIgZm9yIHRoZSA8c3Ryb25nPmluaXRpYWwgc3RhdGU8XC9zdHJvbmc+LjxcL3A+XHJcblxyXG48cD5PbiB0aGUgJGokLXRoIGxpbmUgb2YgdGhlIGZvbGxvd2luZyAkUSQgbGluZXMsIHByaW50IHRoZSBhbnN3ZXIgYWZ0ZXIgJGokLXRoIG1vZGlmaWNhdGlvbiByZXF1ZXN0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Ob3RlIHRoYXQgaXQgaXMmbmJzcDtwb3NzaWJsZSB0aGF0IHRoZSBzdGF0ZSBiZWZvcmUgYW5kIGFmdGVyIGEgbW9kaWZpY2F0aW9uIHJlcXVlc3QgYmUgdGhlIHNhbWUuIEluIG90aGVyIHdvcmRzLCZuYnNwOyRjJiMzOTtfaj1jX3txX2p9OyQmbmJzcDskcyYjMzk7X2o9c197cV9qfSQgY2FuIGhvbGQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZXEgTixRXFxsZXEgMlxcdGltZXMgMTBeNSQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBxX2pcXGxlcSBOJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIGNfaSxzX2ksYyYjMzk7X2oscyYjMzk7X2pcXGxlcSAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiwgUSBcXGxlcSAyNTAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JHMmIzM5O19qJCBpcyBub3QgbW9kaWZpZWQuIEluIG90aGVyIHdvcmRzLCZuYnNwOyRzJiMzOTtfaiZuYnNwOz0gc197cV9qfSQuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzPFwvcD5cclxuIn1d