시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 32 MB 1 1 (100%) 1
문제
밀코는 곰처럼 배고팠는데, 무시하고, 프로그래머와 현지 식당을 우연히 발견했다. 식당에는 N개의 메뉴를 흥미로운 가격정책으로 판매한다: 각 i번음식은 두 가격이 책정된다, Ai와 Bi. 밀코가 첫번재 주문하는 음식은 A가격을 받고, 다른 모든 음식은 B가격을 받는다. 밀코는 얼마나 음식을 주문할지 결정하지 못했다. 더 쉽게 결정하기 위해, 그는 컴퓨터에게 묻기로 했는데, 각각 1에서 N사이의 (포함) k에 대해, k개의 음식을 시키는데 필요한 최소가격이다. 밀코는 음식을 어떤순서로 시켰는지 전혀 신경쓰지 않지만, 같은 음식을 두번 시키고 싶지는 않다. 주문해라, 주문해라, 주문해라.
입력
첫번째 줄에 양의 정수 N (2<=N<=500 000), 음식점에서 판매하는 서로 다른 음식종류의 수가 주어진다. 각 N개의 줄에 걸쳐서 두개의 음이 아닌 정수 Ai와 Bi(0<=Ai, Bi<=1 000 000 000), 위에서 설명한 i번째 음식의 가격들이 주어진다.
출력
N개의 줄에 걸쳐서, k번째 줄에는 k개의 다른 음식을 시킬대 필요한 최소가격을 출력한다.
힌트
입력예제1 ``` 3 10 5 9 3 10 5 ``` 출력예제1 ``` 9 13 18 ``` 입력예제2 ``` 2 100 1 1 100 ``` 출력예제2 ``` 1 2 ``` 입력예제3 ``` 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ``` 출력예제3 ``` 1000000000 2000000000 3000000000 4000000000 5000000000 ``` 첫번째 예제의 설명 k=1; 밀코는 2번 음식을 시켜 A2=9 가격이 필요하다. k=2; 밀코는 1번 음식을 시켜 A1=10의 가격을 지불하고, 2번 음식을 시켜 B2=3를 지불한다. k=3; 밀코는 1번 음식을 시켜 A1=10의 가격을 지불하고, 2번 음식을 시켜 B2=3, 마지막으로 3번 음식을 시켜 B3=5를 지불한다.