2911번 - 전화 복구 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 370 | 207 | 178 | 56.329% |
문제
민혁이는 한 도시의 시장으로 취임했다. 민혁이는 제일 먼저 사람들이 전화를 몇 통하는지 알아보려고 한다.
이 도시에는 동서를 잇는 긴 도로가 하나 있고, 그 도로를 따라서 집이 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
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호