시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB28131147.826%

문제

현주는 안암에서 피자가게를 하고 있다. 이 피자 가게는 환상적인 맛으로 대전에서 엄청난 인기를 끌었고, 대전에 사는 모든 사람들은 점심으로 현주네 피자가게를 이용한다. 현주네 피자가게에서 배달부로 일하는 현정이는 전국 스쿠터 배달 대회 1등 출신이다. 1등 출신 답게 그가 피자를 배달하는데 걸리는 시간은 0에 매우 가깝기 때문에 무시할 수 있다.

배달은 현정이를 통해서 해결하면 되지만, 문제는 피자를 만드는데 시간이 오래걸린다는 것이다. 사람들이 가장 좋아하는 피자의 토핑 조합은 사람마다 다르다. 또, 현주네 가게에 있는 오븐은 매우 작아서 한번에 피자 하나만 구울 수 있다. 따라서, 피자를 굽는 일정을 정하기 위해서 요즘 동혁이를 영입하였다.

동혁이는 날이 시작하기 전에 피자를 만드는 일정을 작성해야 한다.

대전에는 총 N명이 살고 있다. 현주는 모든 사람들에게 고유 번호를 붙여주었고, 번호는 1부터 N까지이다. 동혁이는 일을 시작하기 전에 미리 i가 좋아하는 피자를 만드는데 걸리는 시간(Ti)을 조사했고, 점심을 먹기 원하는 시간(Li)를 조사했다. 만약 피자를 Li보다 K분 빠른 시간에 배달한다면, 현정이는 팁으로 K원을 받게 된다. 또, K분 늦게 배달한다면, 현정이는 K원을 뺏기게 된다. 피자가 정확한 시간에 도착한다면, 팁도 받을 수 없고, 뺏기는 돈도 없다.

동혁이는 학비를 내느라 고생하는 현정이를 위해서, 현정이가 팁을 가능한 많이 받게 일정을 작성하려고 한다. 물론, 현정이가 받는 팁은 음수일 수도 있다. 이러한 경우는 피자를 늦게 배달해서 벌금으로 내는 돈이 더 많을 때이다.

그런데, 가끔 변화를 주기 위해서 좋아하는 피자를 바꾸는 사람도 있다. 이렇게 좋아하는 피자가 바뀔 때는, 원하는 점심 시간이 변할 수도 있다. 이렇게 시키려는 피자를 바꾸려면, 시간이 0일 때 현주네 피자가게로 전화를 해야 한다.

시간이 0인 시간은 피자를 굽기 시작하기 전까지 무한히 지속된다고 한다. 또, 모든 전화는 시간이 0인 동안 온다.

가장 먼저 원래 사람들이 시키려고 한 피자의 정보로 일정을 구한다. 그 다음에, 좋아하는 피자를 바꾸는 전화가 올 때 마다, 일정을 다시 구하는 프로그램을 작성하시오. 동혁이는 현정이가 받는 팁이 가장 커지게 일정을 작성해야 한다.

입력

첫째 줄에 사람의 수 N과 현주가 받은 전화의 수 C가 주어진다.

둘째 줄부터 N개의 줄에는 i가 점심을 먹는 시간 Li와 그가 좋아하는 피자를 굽는데 드는 시간 Ti가 주어진다.

다음 C개 줄에는 세 정수 R(전화를 건 사람의 번호), L(R이 점심을 먹을 새로운 시간), T(R이 좋아하는 피자를 굽는데 드는 시간)이 전화가 온 순서대로 주어진다.

출력

첫째 줄에 아무 전화도 받지 않았을 때, 현정이가 받게되는 최대 팁을 출력한다.

다음 줄부터 C개 줄에는, 각 전화에 의해서 변경되는 일정에서 현정이가 받게되는 최대 팁을 출력한다.

제한

  • 1 ≤ N,C ≤ 200,000
  • 0 ≤ Li, L ≤ 100,000
  • 1 ≤ Ti, T ≤ 100,000
  • 1 ≤ R ≤ N

예제 입력 1

3 2
10 2
6 5
4 3
1 6 1
3 0 10

예제 출력 1

3
2
-11

예제 입력 2

4 2
3 2
0 3
4 3
4 1
3 0 4
1 4 5

예제 출력 2

-8
-13
-18

예제 입력 3

6 7
17 5
26 4
5 5
12 4
8 1
18 2
3 31 3
4 11 5
4 19 3
5 23 2
6 15 1
5 19 1
3 10 4

예제 출력 3

27
59
56
69
78
81
82
58
W3sicHJvYmxlbV9pZCI6IjI4MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MDRcdWM4ZmNcdWIxMjQgXHVkNTNjXHVjNzkwIFx1YWMwMFx1YWM4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjA0XHVjOGZjXHViMjk0IFx1YzU0OFx1YzU1NFx1YzVkMFx1YzExYyBcdWQ1M2NcdWM3OTBcdWFjMDBcdWFjOGNcdWI5N2MgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDUzY1x1Yzc5MCBcdWFjMDBcdWFjOGNcdWIyOTQgXHVkNjU4XHVjMGMxXHVjODAxXHVjNzc4IFx1YjlkYlx1YzczY1x1Yjg1YyBcdWIzMDBcdWM4MDRcdWM1ZDBcdWMxMWMgXHVjNWM0XHVjY2FkXHViMDljIFx1Yzc3OFx1YWUzMFx1Yjk3YyBcdWIwNGNcdWM1YzhcdWFjZTAsIFx1YjMwMFx1YzgwNFx1YzVkMCBcdWMwYWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWM4MTBcdWMyZWNcdWM3M2NcdWI4NWMgXHVkNjA0XHVjOGZjXHViMTI0IFx1ZDUzY1x1Yzc5MFx1YWMwMFx1YWM4Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDYwNFx1YzhmY1x1YjEyNCBcdWQ1M2NcdWM3OTBcdWFjMDBcdWFjOGNcdWM1ZDBcdWMxMWMgXHViYzMwXHViMmVjXHViZDgwXHViODVjIFx1Yzc3Y1x1ZDU1OFx1YjI5NCBcdWQ2MDRcdWM4MTVcdWM3NzRcdWIyOTQgXHVjODA0XHVhZDZkIFx1YzJhNFx1Y2ZlMFx1ZDEzMCBcdWJjMzBcdWIyZWMgXHViMzAwXHVkNjhjIDFcdWI0ZjEgXHVjZDljXHVjMmUwXHVjNzc0XHViMmU0LiAxXHViNGYxIFx1Y2Q5Y1x1YzJlMCBcdWIyZjVcdWFjOGMmbmJzcDtcdWFkZjhcdWFjMDAgXHVkNTNjXHVjNzkwXHViOTdjIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIDBcdWM1ZDAgXHViOWU0XHVjNmIwIFx1YWMwMFx1YWU1ZFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYjM0XHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YjJlY1x1Yzc0MCBcdWQ2MDRcdWM4MTVcdWM3NzRcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YmE3NCBcdWI0MThcdWM5YzBcdWI5Y2MsIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWQ1M2NcdWM3OTBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM2MjRcdWI3OThcdWFjNzhcdWI5YjBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWQ1M2NcdWM3OTBcdWM3NTggXHVkMWEwXHVkNTUxIFx1Yzg3MFx1ZDU2OVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWI5YzhcdWIyZTQgXHViMmU0XHViOTc0XHViMmU0LiBcdWI2MTAsIFx1ZDYwNFx1YzhmY1x1YjEyNCBcdWFjMDBcdWFjOGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzYyNFx1YmUxMFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNzkxXHVjNTQ0XHVjMTFjIFx1ZDU1Y1x1YmM4OFx1YzVkMCBcdWQ1M2NcdWM3OTAgXHVkNTU4XHViMDk4XHViOWNjIFx1YWQ2Y1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWFkN2RcdWIyOTQgXHVjNzdjXHVjODE1XHVjNzQ0IFx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNjk0XHVjOTk4Jm5ic3A7XHViM2Q5XHVkNjAxXHVjNzc0XHViOTdjIFx1YzYwMVx1Yzc4NVx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YjBhMFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzdjXHVjODE1XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjMwMFx1YzgwNFx1YzVkMFx1YjI5NCBcdWNkMWQgTlx1YmE4NVx1Yzc3NCBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM4ZmNcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWFjZTBcdWM3MjAgXHViYzg4XHVkNjM4XHViOTdjIFx1YmQ5OVx1YzVlY1x1YzhmY1x1YzVjOFx1YWNlMCwgXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMFx1Yzc3NFx1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc3Y1x1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmJmOFx1YjlhYyBpXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWQ1M2NcdWM3OTBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQoVDxzdWI+aTxcL3N1Yj4pXHVjNzQ0IFx1Yzg3MFx1YzBhY1x1ZDU4OFx1YWNlMCwgXHVjODEwXHVjMmVjXHVjNzQ0IFx1YmEzOVx1YWUzMCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0KEw8c3ViPmk8XC9zdWI+KVx1Yjk3YyBcdWM4NzBcdWMwYWNcdWQ1ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQ1M2NcdWM3OTBcdWI5N2MgTDxzdWI+aTxcL3N1Yj5cdWJjZjRcdWIyZTQgS1x1YmQ4NCBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmMzMFx1YjJlY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVkNjA0XHVjODE1XHVjNzc0XHViMjk0Jm5ic3A7XHVkMzAxXHVjNzNjXHViODVjIEtcdWM2ZDBcdWM3NDQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwLCBLXHViZDg0IFx1YjJhNlx1YWM4YyBcdWJjMzBcdWIyZWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1ZDYwNFx1YzgxNVx1Yzc3NFx1YjI5NCBLXHVjNmQwXHVjNzQ0IFx1YmU4Zlx1YWUzMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDUzY1x1Yzc5MFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVkMzAxXHViM2M0IFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWJlOGZcdWFlMzBcdWIyOTQgXHViM2M4XHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1ZDU1OVx1YmU0NFx1Yjk3YyBcdWIwYjRcdWIyOTBcdWI3N2MgXHVhY2UwXHVjMGRkXHVkNTU4XHViMjk0IFx1ZDYwNFx1YzgxNVx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1ZDYwNFx1YzgxNVx1Yzc3NFx1YWMwMCBcdWQzMDFcdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjljZVx1Yzc3NCBcdWJjMWJcdWFjOGMgXHVjNzdjXHVjODE1XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCwgXHVkNjA0XHVjODE1XHVjNzc0XHVhYzAwIFx1YmMxYlx1YjI5NCBcdWQzMDFcdWM3NDAgXHVjNzRjXHVjMjE4XHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWIyOTQgXHVkNTNjXHVjNzkwXHViOTdjIFx1YjJhNlx1YWM4YyBcdWJjMzBcdWIyZWNcdWQ1NzRcdWMxMWMgXHViYzhjXHVhZTA4XHVjNzNjXHViODVjIFx1YjBiNFx1YjI5NCBcdWIzYzhcdWM3NzQgXHViMzU0IFx1YjljZVx1Yzc0NCBcdWI1NGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCwgXHVhYzAwXHViMDU0IFx1YmNjMFx1ZDY1NFx1Yjk3YyBcdWM4ZmNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWQ1M2NcdWM3OTBcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTNjXHVjNzkwXHVhYzAwIFx1YmMxNFx1YjAxNCBcdWI1NGNcdWIyOTQsIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM4MTBcdWMyZWMgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YmNjMFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMmRjXHVkMGE0XHViODI0XHViMjk0IFx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWJjMTRcdWFmYjhcdWI4MjRcdWJhNzQsIFx1YzJkY1x1YWMwNFx1Yzc3NCAwXHVjNzdjIFx1YjU0YyBcdWQ2MDRcdWM4ZmNcdWIxMjQgXHVkNTNjXHVjNzkwXHVhYzAwXHVhYzhjXHViODVjIFx1YzgwNFx1ZDY1NFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWFjMDRcdWM3NzQgMFx1Yzc3OCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVkNTNjXHVjNzkwXHViOTdjIFx1YWQ3ZFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVhZTRjXHVjOWMwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWM5YzBcdWMxOGRcdWI0MWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWQ2NTRcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IDBcdWM3NzggXHViM2Q5XHVjNTQ4IFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCBcdWM2ZDBcdWI3OTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzJkY1x1ZDBhNFx1YjgyNFx1YWNlMCBcdWQ1NWMgXHVkNTNjXHVjNzkwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjg1YyBcdWM3N2NcdWM4MTVcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwLCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTNjXHVjNzkwXHViOTdjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWM4MDRcdWQ2NTRcdWFjMDAgXHVjNjJjIFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1Yzc3Y1x1YzgxNVx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2MDRcdWM4MTVcdWM3NzRcdWFjMDAgXHViYzFiXHViMjk0IFx1ZDMwMVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjZWU0XHVjOWMwXHVhYzhjIFx1Yzc3Y1x1YzgxNVx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVkNjA0XHVjOGZjXHVhYzAwJm5ic3A7XHViYzFiXHVjNzQwIFx1YzgwNFx1ZDY1NFx1Yzc1OCBcdWMyMTggQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YWMwMCBcdWM4MTBcdWMyZWNcdWM3NDQgXHViYTM5XHViMjk0IFx1YzJkY1x1YWMwNCBMPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWFkZjhcdWFjMDAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWFkN2RcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YzJkY1x1YWMwNCBUPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBDXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IFIoXHVjODA0XHVkNjU0XHViOTdjIFx1YWM3NCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4KSwgTChSXHVjNzc0IFx1YzgxMFx1YzJlY1x1Yzc0NCBcdWJhMzlcdWM3NDQgXHVjMGM4XHViODVjXHVjNmI0IFx1YzJkY1x1YWMwNCksIFQoUlx1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTNjXHVjNzkwXHViOTdjIFx1YWQ3ZFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0KVx1Yzc3NCBcdWM4MDRcdWQ2NTRcdWFjMDAgXHVjNjI4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1NDRcdWJiMzQgXHVjODA0XHVkNjU0XHViM2M0IFx1YmMxYlx1YzljMCBcdWM1NGFcdWM1NThcdWM3NDQgXHViNTRjLCBcdWQ2MDRcdWM4MTVcdWM3NzRcdWFjMDAmbmJzcDtcdWJjMWJcdWFjOGNcdWI0MThcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDMwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgQ1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1YWMwMSBcdWM4MDRcdWQ2NTRcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjIFx1YmNjMFx1YWNiZFx1YjQxOFx1YjI5NCBcdWM3N2NcdWM4MTVcdWM1ZDBcdWMxMWMgXHVkNjA0XHVjODE1XHVjNzc0XHVhYzAwIFx1YmMxYlx1YWM4Y1x1YjQxOFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkMzAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4sQyAmbGU7IDIwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IEw8c3ViPmk8XC9zdWI+LCBMICZsZTsgMTAwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgVDxzdWI+aTxcL3N1Yj4sIFQgJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBSICZsZTsgTjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjgyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJBU1BPUkVEIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyZyc3F1bztzIHBpenphIHBsYWNlIGlzIHRoZSBiZXN0IG9uZSBpbiB0b3duLiBJdCBpcyBzbyBnb29kIHRoYXQgYWxsIHRvd24gcmVzaWRlbnRzIGVhdCBwaXp6YSBmb3IgbHVuY2ggZXZlcnkgZGF5LiBNaXJrbyZyc3F1bztzIGRlbGl2ZXJ5IHNlcnZpY2UgaXMgc28gZmFzdCB0aGF0IHRoZSBkZWxpdmVyeSB0aW1lIGlzIG5lZ2xpZ2libGUuIFRoZSBwcm9ibGVtIGlzIGJha2luZyB0aGUgcGl6emFzLCBzaW5jZSBhbGwgcmVzaWRlbnRzIGhhdmUgdGhlaXIgb3duIGZhdm91cml0ZSB0b3BwaW5nIGNvbWJpbmF0aW9uLCBzbyBiYWtpbmcgcGl6emFzIGZvciB0d28gZGlmZmVyZW50IHJlc2lkZW50cyBkb2VzbiZyc3F1bzt0IGFsd2F5cyB0YWtlIHRoZSBzYW1lIGFtb3VudCBvZiB0aW1lLiBNaXJrbyBvbmx5IGhhcyBvbmUgc21hbGwgYmFraW5nIG92ZW4gd2l0aCBhIGNhcGFjaXR5IG9mIGEgc2luZ2xlIHBpenphIGF0IGEgdGltZSwgc28gZ29vZCBzY2hlZHVsaW5nIGlzIGV4dHJlbWVseSBpbXBvcnRhbnQgYW5kIG11c3QgYmUgZGV0ZXJtaW5lZCBiZWZvcmUgdGhlIGRheSBzdGFydHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIG9mIHRoZSBOIHRvd24gcmVzaWRlbnRzIChkZW5vdGVkIGJ5IG51bWJlcnMgZnJvbSAxIHRvIE4pIHdlIGtub3cgdGhlIGJha2luZyBkdXJhdGlvbiBmb3IgdGhlaXIgZmF2b3VyaXRlIHBpenphIChUaSksIGFzIHdlbGwgYXMgdGhlIG1vbWVudCBpbiB0aGUgZGF5IHdoZW4gdGhleSBwbGFuIG9uIGhhdmluZyBsdW5jaCAoTGkpLiBJZiBhIHJlc2lkZW50IHJlY2VpdmVzIHRoZWlyIHBpenphIEsgbW9tZW50cyBiZWZvcmUgdGhlIHBsYW5uZWQgbHVuY2ggdGltZSwgTWlya28gaXMgcmV3YXJkZWQgd2l0aCBhIHRpcCBvZiBLIGt1bmFzLiBPbiB0aGUgb3RoZXIgaGFuZCwgaWYgdGhlIHBpenphIGlzIGRlbGl2ZXJlZCBLIG1vbWVudHMgbGF0ZSAoYWZ0ZXIgdGhlIHBsYW5uZWQgbHVuY2ggdGltZSksIE1pcmtvIG11c3QgcGF5IHRoZSByZXNpZGVudCBLIGt1bmFzIChiZWNhdXNlIG9mIGhpcyB0aW1lbHkgZGVsaXZlcnkgaW5zdXJhbmNlIHBvbGljeSkuIElmIHRoZSBwaXp6YSBpcyBkZWxpdmVyZWQgcHJlY2lzZWx5IG9uIHRpbWUsIE1pcmtvIHdvbiZyc3F1bzt0IGdldCBhIHRpcCwgYnV0IGhlIGRvZXNuJnJzcXVvO3QgaGF2ZSB0byBwYXkgYW55dGhpbmcgZWl0aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyB3b3VsZCBsaWtlIHRvIGtub3cgdGhlIG1heGltdW0gdG90YWwgdGlwIChpbmNsdWRpbmcgYWxsIGluc3VyYW5jZSBwYXlvdXRzIGFzIG5lZ2F0aXZlIHRpcHMpIHRoYXQgY2FuIGJlIGVhcm5lZCBpbiBhIGRheSBpZiBwaXp6YXMgYXJlIGJha2VkIGluIGFuIG9wdGltYWwgb3JkZXIuIE5vdGljZSB0aGF0IE1pcmtvIGNhbiBlYXJuIGEgbmVnYXRpdmUgdG90YWwgdGlwIChpZiBoZSBoYXMgdG8gcGF5IG91dCBtb3JlIGluc3VyYW5jZSB0aGFuIHRoZSBhbW91bnQgb2YgdGlwcyBoZSByZWNlaXZlcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNpbmNlIHJlc2lkZW50cyBzb21ldGltZXMgY2hhbmdlIHRoZWlyIGZhdm91cml0ZSBwaXp6YSB0b3BwaW5ncywgYXMgd2VsbCBhcyB0aGVpciBwcmVmZXJyZWQgbHVuY2ggdGltZSwgTWlya28mcnNxdW87cyBzY2hlZHVsZSBtdXN0IGJlIGFkYXB0ZWQgaW4gb3JkZXIgdG8ga2VlcCBlYXJuaW5nIG9wdGltYWwgdGlwIGFtb3VudHMuIFdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBtYXhpbXVtIHRvdGFsIHRpcCBmb3IgdGhlIGJlZ2lubmluZyByZXF1aXJlbWVudHMsIGFzIHdlbGwgYXMgYWZ0ZXIgZWFjaCBjaGFuZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IEluIHRoaXMgdG93biwgdGhlIGRheSBzdGFydHMgYXQgdGhlIG1vbWVudCB0ID0gMCBhbmQgbGFzdHMgbXVjaCBsb25nZXIgdGhhbiB0aGUgdGltZSBuZWVkZWQgdG8gYmFrZSBwaXp6YXMgZm9yIGFsbCByZXNpZGVudHMuIFRoZSBzY2hlZHVsZSwgaW5jbHVkaW5nIHRoZSBhZGFwdGF0aW9ucywgbXVzdCBiZSBkZXRlcm1pbmVkIGJlZm9yZSB0aGUgZGF5IHN0YXJ0cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBOIGFuZCBDLCB0aGUgbnVtYmVyIG9mIHJlc2lkZW50cyBhbmQgdGhlIG51bWJlciBvZiBwaXp6YSByZXF1aXJlbWVudCBjaGFuZ2VzLCByZXNwZWN0aXZlbHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnM6IExpLCB0aGUgbW9tZW50IHdoZW4gcmVzaWRlbnQgaSBwbGFucyBvbiBoYXZpbmcgbHVuY2gsIGFuZCBUaSwgdGhlIHRpbWUgbmVlZGVkIHRvIGJha2UgdGhlIHBpenphIGZvciByZXNpZGVudCBpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IEMgbGluZXMgY29udGFpbnMgdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnM6IFIgKHRoZSBpbmRleCBvZiBhIHJlc2lkZW50KSwgTCAodGhlIG5ldyBtb21lbnQgd2hlbiByZXNpZGVudCBSIHBsYW5zIG9uIGhhdmluZyBsdW5jaCksIGFuZCBUICh0aGUgdGltZSBuZWVkZWQgdG8gYmFrZSByZXNpZGVudCBSJnJzcXVvO3MgbmV3IGZhdm91cml0ZSBwaXp6YSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWF4aW11bSB0b3RhbCB0aXAgZm9yIHRoZSBiZWdpbm5pbmcgcmVxdWlyZW1lbnRzIG9mIHRoZSByZXNpZGVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIG9mIHRoZSBDIGNoYW5nZXMsIHRoZSBvdXRwdXQgbXVzdCBjb250YWluIGFuIGFkZGl0aW9uYWwgbGluZSBvZiBvdXRwdXQgY29udGFpbmluZyB0aGUgbmV3IG1heGltdW0gdG90YWwgdGlwIHZhbHVlIGFmdGVyIHRoZSBjaGFuZ2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkZpcnN0IHNhbXBsZSBkZXNjcmlwdGlvbjogVGhlIG9wdGltYWwgcGl6emEgYmFraW5nIHNjaGVkdWxlIGlzICgxLCAzLCAyKS4gVGhhdCB3YXksIHRoZSBmaXJzdCBwaXp6YSB3aWxsIGJlIGZpbmlzaGVkIGF0IHRoZSBtb21lbnQgdCA9IDIsIHRoZSB0aGlyZCBvbmUgYXQgdCA9IDUsIGFuZCB0aGUgc2Vjb25kIG9uZSBhdCB0ID0gMTAuIFRoZSBmaXJzdCBwaXp6YSB3aWxsIGJlIGRlbGl2ZXJlZCA4IG1vbWVudHMgZWFybHkgKDgga3VuYXMgdGlwKSwgdGhlIHNlY29uZCBvbmUgd2lsbCBiZSAxIG1vbWVudCBsYXRlICgtMSBrdW5hKSwgYW5kIHRoZSB0aGlyZCBvbmUgd2lsbCBiZSA0IG1vbWVudHMgbGF0ZSAoLTQga3VuYXMpLCBzbyB0aGUgdG90YWwgdGlwIGlzIDMga3VuYXMuIFdoZW4gdGhlIGZpcnN0IHJlc2lkZW50IGNoYW5nZXMgcmVxdWlyZW1lbnRzLCB0aGUgb3B0aW1hbCBzY2hlZHVsZSByZW1haW5zIHVuY2hhbmdlZCwgd2hpbGUgdGhlIHRpcHMgY2hhbmdlIHRvIDUsIDAsIGFuZCAtMywgcmVzcGVjdGl2ZWx5LiBBZnRlciB0aGUgc2Vjb25kIHJlcXVpcmVtZW50IGNoYW5nZSwgdGhlIG9wdGltYWwgc2NoZWR1bGUgaXMgKDEsIDIsIDMpLCB3aGlsZSB0aGUgdGlwcyBhcmUgNSwgMCwgYW5kIC0xNiwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiwgQyAmbGU7IDIwMCAwMDAsJm5ic3A7PFwvbGk+XHJcblx0PGxpPjAgJmxlOyBMPHN1Yj5pPFwvc3ViPiwgTCAmbGU7IDEwMCAwMDAsJm5ic3A7PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBUPHN1Yj5pPFwvc3ViPiwgVCAmbGU7IDEwMCAwMDAsJm5ic3A7PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBSICZsZTsgTi48XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 6번