시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 28 28 51.852%

문제

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

이 도시에는 동서를 잇는 긴 도로가 하나 있고, 그 도로를 따라서 집이 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 사이에 설치되었다는 뜻이다. 같은 장소에 감지기가 여러 개 설치되어 있는 경우는 없다.

출력

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

예제 입력

3 4 
3 1 
2 2 
1 1

예제 출력

2

예제 입력 2

2 3
1 23
2 17

예제 출력 2

23

예제 입력 3

3 9
7 2
8 3
3 4

예제 출력 3

5

힌트

출처

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

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