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

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 인간들이 자주 즐겨먹는 과자인 “프링글스”를 발견하게 되었다. 그리고 그 원숭이는 결국 뚜껑을 열어버렸다.ㅠㅠ 불쌍한 원숭이. 이제 그는 절대 멈출 수 없다.

원숭이가 새로운 맛의 프링글스를 먹을 때 마다 원숭이는 중독스트레스를 스스로 조절한다. 그런데 각 맛마다 중독스트레스를 조절할 수 있는 범위가 정해져 있어서 그 범위 내에서만 조절이 가능하다.

그런데 원숭이는 참 슬프게도 중독스트레스를 조절할 때 마다 예상수명이 1년씩 줄어든다. 예를 들어서 중독스트레스의 값이 5였는데 그것을 3이나 7로 조절하였다면 예상수명이 2년이나 줄어들게 되는 것이다.ㅠㅠ

원숭이는 N개의 서로 다른 맛의 프링글스 뚜껑을 모두 열어버렸으므로 이제 멈출 수 없다. N개의 서로 다른 맛의 프링글스를 순서대로 먹어야 한다. 프링글스를 하나도 먹지 않았을 때는 중독스트레스의 값을 원숭이 마음대로 조절할 수 있다. 프링글스를 한통씩 먹으면서 원숭이가 중독스트레스를 조절하는데 그때 예상수명이 줄어드는 것을 최소화하는 프로그램을 작성하시오.

입력

첫째 줄에 프링글스 맛의 개수 N이 주어진다. N은 1이상 100,000이하인 정수이다. 그 다음 줄부터 N줄에 걸쳐 두 개의 정수 si, ei (1 ≤ si ≤ ei ≤ 200)가 주어지는데, i번째 프링글스 맛의 중독스트레스 조절범위가 si이상 ei이하라는 뜻이다. 프링글스를 먹을 때에는 입력에서 주어진 순서대로 먹어야 한다.

출력

첫째 줄에 원숭이의 줄어든 예상수명의 양의 최솟값을 출력한다. 그 다음 줄부터 N줄에 걸쳐 각 프링글스를 먹을 때 조절한 중독 스트레스의 값을 출력하시오.

예제 입력 1

5
1 5
16 25
3 7
1 100
37 49

예제 출력 1

50
5
16
7
7
37

출처

  • 문제를 만든 사람: ntopia