시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 119 42 31 39.241%

문제

상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 N개 팔고 있고, 손님은 서로 다른 음식을 여러개 시킬 수 있다. 이 때, 음식을 시키는 순서가 중요하다. 그 이유는 각 음식을 첫번째로 시킬 때의 가격과 아닐 때의 가격이 다르기 때문이다. 즉, 모든 음식 i의 가격은 첫 번째로 시킬 때의 가격 Ai와 아닐 때의 가격 Bi 두가지가 있다.

배가 고픈 창영이는 상근이네 레스토랑에서 음식을 시켜먹으려고 한다. 이 때, 1개, 2개, ..., N개 시킬 때 필요한 최소 가격을 각각 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 1,000,000,000)

출력

출력은 총 N개로 이루어져 있다. i번째 줄에는 음식을 i개 시킬 때 필요한 최소 가격을 출력한다.

예제 입력

3
10 5
9 3
10 5

예제 출력

9
13
18

힌트

음식을 1개 시킬 때는, 2번을 시키면 된다. (9)

음식을 2개 시킬 때는, 1번을 시키고, 2번을 시키면 된다. (10+3)

음식을 3개 시킬 때는, 1번을 시키고, 2번, 3번을 시키면 된다. (10+3+5)