시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 177 88 82 52.229%

문제

민혁이는 한 도시의 시장으로 취임했다. 민혁이는 제일 먼저 사람들이 전화를 몇 통하는지 알아보려고 한다.

이 도시에는 동서를 잇는 긴 도로가 하나 있고, 그 도로를 따라서 집이 M개 있다. 가장 서쪽에 있는 집의 번호는 1이고, 이 순서대로 진행한다.

전화 감지기는 두 집 사이에 설치할 수 있다. 감지기는 감지기가 설치된 위치로부터 동쪽에 있는 집과 서쪽에 있는 집이 서로 통화하는것을 감지할 수 있다.

하루가 지나고, 민혁이는 감지기를 모두 회수했다. 이제 하루동안 이 도시에 전화가 몇 통있었는지 알아보려고 한다. 감지기가 설치되었던 위치와 각 감지기엔 감지된 전화 통화의 수가 주어졌을 때, 이 마을에서 전화가 적어도 몇 통 있었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 감지기의 수 N과 집의 수 M이 주어진다. (1 ≤ N ≤ 100,000, N < M ≤ 1,000,000,000)

다음 N개 줄에는 두 수 Pi와 Ci가 주어진다. Pi는 감지기가 설치된 위치이고, Ci는 감지된 전화의 수이다. (1 ≤ Pi < M, 1 ≤ Ci ≤ 1,000,000,000) 감지기가 설치된 위치가 Pi라는 뜻은, Pi와 Pi+1 에 위치한 두 집 사이에 설치되었다는 뜻이다. 같은 장소에 감지기가 여러 개 설치되어 있는 경우는 없다.

출력

첫째 줄에 이 마을에서 하루 동안 전화가 적어도 몇 통 있었는지 출력한다.

예제 입력 1

3 4 
3 1 
2 2 
1 1

예제 출력 1

2

예제 입력 2

2 3
1 23
2 17

예제 출력 2

23

예제 입력 3

3 9
7 2
8 3
3 4

예제 출력 3

5
W3sicHJvYmxlbV9pZCI6IjI5MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWQ2NTQgXHViY2Y1XHVhZDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyZGNcdWM3YTVcdWM3M2NcdWI4NWMgXHVjZGU4XHVjNzg0XHVkNTg4XHViMmU0LiBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjODFjXHVjNzdjIFx1YmEzY1x1YzgwMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjODA0XHVkNjU0XHViOTdjIFx1YmE4NyBcdWQxYjVcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjNjNFx1YzJkY1x1YzVkMFx1YjI5NCBcdWIzZDlcdWMxMWNcdWI5N2MgXHVjNzg3XHViMjk0IFx1YWUzNCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjOWQxXHVjNzc0IE1cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjMTFjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWM3NzRcdWFjZTAsIFx1Yzc3NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MDRcdWQ2NTQgXHVhYzEwXHVjOWMwXHVhZTMwXHViMjk0IFx1YjQ1MCBcdWM5ZDEgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMTBcdWM5YzBcdWFlMzBcdWIyOTQgXHVhYzEwXHVjOWMwXHVhZTMwXHVhYzAwIFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWM3MDRcdWNlNThcdWI4NWNcdWJkODBcdWQxMzAgXHViM2Q5XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWFjZmMgXHVjMTFjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWM3NzQgXHVjMTFjXHViODVjIFx1ZDFiNVx1ZDY1NFx1ZDU1OFx1YjI5NFx1YWM4M1x1Yzc0NCBcdWFjMTBcdWM5YzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViOGU4XHVhYzAwIFx1YzljMFx1YjA5OFx1YWNlMCwgXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YWMxMFx1YzljMFx1YWUzMFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVkNjhjXHVjMjE4XHVkNTg4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVkNTU4XHViOGU4XHViM2Q5XHVjNTQ4IFx1Yzc3NCBcdWIzYzRcdWMyZGNcdWM1ZDAmbmJzcDtcdWM4MDRcdWQ2NTRcdWFjMDAgXHViYTg3IFx1ZDFiNVx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMTBcdWM5YzBcdWFlMzBcdWFjMDAgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWM4XHViMzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWFjMDEgXHVhYzEwXHVjOWMwXHVhZTMwXHVjNWQ0IFx1YWMxMFx1YzljMFx1YjQxYyBcdWM4MDRcdWQ2NTQgXHVkMWI1XHVkNjU0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzgwNFx1ZDY1NFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViYTg3IFx1ZDFiNSBcdWM3ODhcdWM1YzhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMxMFx1YzljMFx1YWUzMFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWM5ZDFcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCBOICZsdDsgTSAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjMjE4IFA8c3ViPmk8XC9zdWI+XHVjNjQwIEM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVhYzEwXHVjOWMwXHVhZTMwXHVhYzAwIFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWM3MDRcdWNlNThcdWM3NzRcdWFjZTAsIEM8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWMxMFx1YzljMFx1YjQxYyBcdWM4MDRcdWQ2NTRcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiAoMSAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsdDsgTSwgMSAmbGU7IEM8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCkgXHVhYzEwXHVjOWMwXHVhZTMwXHVhYzAwIFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWM3MDRcdWNlNThcdWFjMDAgUDxzdWI+aTxcL3N1Yj5cdWI3N2NcdWIyOTQgXHViNzNiXHVjNzQwLCBQPHN1Yj5pPFwvc3ViPlx1YzY0MCBQPHN1Yj5pPFwvc3ViPisxIFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViNDUwIFx1YzlkMSBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YzdhNVx1YzE4Y1x1YzVkMCBcdWFjMTBcdWM5YzBcdWFlMzBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWMxMjRcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NzQgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjhlOCBcdWIzZDlcdWM1NDggXHVjODA0XHVkNjU0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWJhODcgXHVkMWI1IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUkFaR09WT1JJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrb3MgdmlsbGFnZSBoYXMgb25seSBvbmUgbG9uZyBzdHJlZXQgc3RyZXRjaGluZyBmcm9tIGVhc3QgdG8gd2VzdCB3aXRoIE0gaG91c2VzLiBFYWNoIGhvdXNlIGhhcyBhIHVuaXF1ZSBob3VzZSBudW1iZXIsIHN0YXJ0aW5nIHdpdGggMSBhbmQgZW5kaW5nIHdpdGggTS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmVjZW50IHN0b3JtIHRvb2sgb3V0IG1vc3QgcGhvbmUgbGluZXMgc28gdGhlIG1heW9yIGZpbmFuY2VkIGNvbnN0cnVjdGlvbiBvZiBhIG5ldyBvbmUuIE1pcmtvIGlzIGludGVyZXN0ZWQgaW4gdGhlIHBvcHVsYXJpdHkgb2YgdGhpcyBuZXcgcGhvbmUgbmV0d29yaywgc28gaGUgaW5maWx0cmF0ZWQgaXRzIGNvbnN0cnVjdGlvbiBhbmQgcGxhY2VkIHNwZWNpYWwgZGV0ZWN0b3JzIG9uIHNvbWUgcG9pbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EZXRlY3RvciBkZXRlY3RzIGFueSBwaG9uZSBjYWxsIG1hZGUgYmV0d2VlbiB0d28gaG91c2VzLCBhcyBsb25nIGFzIG9uZSBvZiB0aGVtIGlzIGVhc3R3YXJkIGFuZCB0aGUgb3RoZXIgd2VzdHdhcmQgZnJvbSB0aGUgcG9pbnQgdGhlIGRldGVjdG9yIGlzIGluc3RhbGxlZC48XC9wPlxyXG5cclxuPHA+QXQgdGhlIGVuZCBvZiB0aGUgZmlyc3QgbW9udGgsIE1pcmtvIHJlbW92ZWQgYWxsIGRldGVjdG9ycyBhbmQgbm93IHdvbmRlcnMgd2hhdCBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHBob25lIGNhbGxzIHRoYXQgY291bGQgaGF2ZSBiZWVuIG1hZGUgZHVyaW5nIHRoYXQgbW9udGg8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCBudW1iZXIgb2YgZGV0ZWN0b3JzLCBhbmQgTSAoTiAmbHQ7IE0gJmxlOyAxIDAwMCAwMDAgMDAwKSwgbnVtYmVyIG9mIGhvdXNlcyBpbiB0aGUgdmlsbGFnZS48XC9wPlxyXG5cclxuPHA+TmV4dCBOIGxpbmVzIGNvbnRhaW5zIHR3byBudW1iZXJzIGVhY2g6IFA8c3ViPmk8XC9zdWI+ICgxICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmx0OyBNKSwgYW5kIEM8c3ViPmk8XC9zdWI+ICgxICZsZTsgQzxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwKSwgdGhlIHBvc2l0aW9uIGFuZCB0b3RhbCBudW1iZXIgb2YgcGhvbmUgY2FsbHMgZGV0ZWN0ZWQgYnkgZGV0ZWN0b3IgbnVtYmVyZWQgaS4gV2Ugc2F5IHRoYXQgYSBkZXRlY3RvciBpcyBvbiBwb3NpdGlvbiBQPHN1Yj5pPFwvc3ViPiBpZiBhbmQgb25seSBpZiBoZSBpcyBiZXR3ZWVuIGhvdXNlcyBudW1iZXJlZCBQPHN1Yj5pPFwvc3ViPiBhbmQgUDxzdWI+aTxcL3N1Yj4rMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlcmUgd2lsbCBuZXZlciBiZSBtb3JlIHRoYW4gb25lIGRldGVjdG9yIG9uIHRoZSBzYW1lIHBvc2l0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbWluaW1hbCBudW1iZXIgb2YgcGhvbmUgY2FsbHMgbWFkZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #3 4번