시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 120 61 57 54.286%

문제

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

이 도시에는 동서를 잇는 긴 도로가 하나 있고, 그 도로를 따라서 집이 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+aTxcL3N1Yj5cdWI3N2NcdWIyOTQgXHViNzNiXHVjNzQwLCBQPHN1Yj5pPFwvc3ViPlx1YzY0MCBQPHN1Yj5pPFwvc3ViPisxIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWMxMjRcdWNlNThcdWI0MThcdWM1YzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjN2E1XHVjMThjXHVjNWQwIFx1YWMxMFx1YzljMFx1YWUzMFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3NCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHVkNTU4XHViOGU4IFx1YjNkOVx1YzU0OCBcdWM4MDRcdWQ2NTRcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1YmE4NyBcdWQxYjUgXHVjNzg4XHVjNWM4XHViMjk0XHVjOWMwJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5MTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSQVpHT1ZPUkkiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvcyB2aWxsYWdlIGhhcyBvbmx5IG9uZSBsb25nIHN0cmVldCBzdHJldGNoaW5nIGZyb20gZWFzdCB0byB3ZXN0IHdpdGggTSBob3VzZXMuIEVhY2ggaG91c2UgaGFzIGEgdW5pcXVlIGhvdXNlIG51bWJlciwgc3RhcnRpbmcgd2l0aCAxIGFuZCBlbmRpbmcgd2l0aCBNLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZWNlbnQgc3Rvcm0gdG9vayBvdXQgbW9zdCBwaG9uZSBsaW5lcyBzbyB0aGUgbWF5b3IgZmluYW5jZWQgY29uc3RydWN0aW9uIG9mIGEgbmV3IG9uZS4gTWlya28gaXMgaW50ZXJlc3RlZCBpbiB0aGUgcG9wdWxhcml0eSBvZiB0aGlzIG5ldyBwaG9uZSBuZXR3b3JrLCBzbyBoZSBpbmZpbHRyYXRlZCBpdHMgY29uc3RydWN0aW9uIGFuZCBwbGFjZWQgc3BlY2lhbCBkZXRlY3RvcnMgb24gc29tZSBwb2ludHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRldGVjdG9yIGRldGVjdHMgYW55IHBob25lIGNhbGwgbWFkZSBiZXR3ZWVuIHR3byBob3VzZXMsIGFzIGxvbmcgYXMgb25lIG9mIHRoZW0gaXMgZWFzdHdhcmQgYW5kIHRoZSBvdGhlciB3ZXN0d2FyZCBmcm9tIHRoZSBwb2ludCB0aGUgZGV0ZWN0b3IgaXMgaW5zdGFsbGVkLjxcL3A+XHJcblxyXG48cD5BdCB0aGUgZW5kIG9mIHRoZSBmaXJzdCBtb250aCwgTWlya28gcmVtb3ZlZCBhbGwgZGV0ZWN0b3JzIGFuZCBub3cgd29uZGVycyB3aGF0IGlzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgcGhvbmUgY2FsbHMgdGhhdCBjb3VsZCBoYXZlIGJlZW4gbWFkZSBkdXJpbmcgdGhhdCBtb250aDxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiBkZXRlY3RvcnMsIGFuZCBNIChOICZsdDsgTSAmbGU7IDEgMDAwIDAwMCAwMDApLCBudW1iZXIgb2YgaG91c2VzIGluIHRoZSB2aWxsYWdlLjxcL3A+XHJcblxyXG48cD5OZXh0IE4gbGluZXMgY29udGFpbnMgdHdvIG51bWJlcnMgZWFjaDogUDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbHQ7IE0pLCBhbmQgQzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDApLCB0aGUgcG9zaXRpb24gYW5kIHRvdGFsIG51bWJlciBvZiBwaG9uZSBjYWxscyBkZXRlY3RlZCBieSBkZXRlY3RvciBudW1iZXJlZCBpLiBXZSBzYXkgdGhhdCBhIGRldGVjdG9yIGlzIG9uIHBvc2l0aW9uIFA8c3ViPmk8XC9zdWI+IGlmIGFuZCBvbmx5IGlmIGhlIGlzIGJldHdlZW4gaG91c2VzIG51bWJlcmVkIFA8c3ViPmk8XC9zdWI+IGFuZCBQPHN1Yj5pPFwvc3ViPisxLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSB3aWxsIG5ldmVyIGJlIG1vcmUgdGhhbiBvbmUgZGV0ZWN0b3Igb24gdGhlIHNhbWUgcG9zaXRpb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIHRoZSBtaW5pbWFsIG51bWJlciBvZiBwaG9uZSBjYWxscyBtYWRlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: flrngel
  • 잘못된 번역을 찾은 사람: kesakiyo