COCI 2012/2013 contest 2 task 4 Popust- 피자가게 > 문제은행 : 정보올림피아드&알고리즘




1798 : 피자가게

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
10 회   
시도횟수
105 회   

문제

준호는 올해 정올 본선에 진출하게 된 기념으로 대형 피자를 하나 사서 친구들과 나누어 먹으려고 한다. 

피자를 먹으려면 음료수도 필요할 거 같아 친구들에게 음료수도 한 개씩 사서 주려고 한다. 

그런데 준호는 음료수를 싫어하기 때문에 자기 것은 살 필요가 없다. 

그리고 친구들중에는 음료수를 싫어하는 친구들이 몇 명이나 있을지 알 수가 없다.


모든 친구가 음료수를 싫어한다면 0개를 사야 하고 준호만 음료수를 싫어한다면 N-1개를 사야 한다. 

그래서 음료수를 0개를 사는 경우부터 N-1개를 사는 경우까지 각각의 최소 비용을 구해 보기로 했다.


그런데 또 한가지 문제가 생겼다.


동네에 있는 모든 피자가게에서 음료수도 팔지만 한 가게에서는 피자든 음료수든 한 개 밖에는 팔지 않기로 합의를 했다는 것이다. 

즉 한 가게에서 피자와 음료수를 동시에 살 수가 없고 음료수도 두 개 이상 살수가 없다는 것이다.

 


따라서 준호는 N개의 가게에 들러 그중 한 곳에서는 피자를 사고 나머지 가게에서는 음료수를 한 개씩 살 수밖에 없다.


학생수 N과 준호가 들른 N개의 가게에서 판매하는 피자의 가격 Hi, 음료수의 가격 Ai 가 주어질 때 피자 1개를 포함하여 0~N-1개의 음료수를 사기위한 각각의 최소비용을 구하여 출력하는 프로그램을 작성하라.


입력형식

첫 번째 줄에는 N (2 ≤ N ≤ 500,000) 이 주어진다.
두 번째 줄부터 N개의 줄에는 각 가게에서 파는 피자와 음료수의 가격 Hi 와 Ai 가 주어진다.

(1 <= Hi, Ai <= 1,000,000,000)

출력형식

N줄에 걸쳐 피자 1개를 포함하여 음료수 0개를 살 때의 비용부터 N-1개 살때까지의 각각의 최소 비용을 한줄에 하나씩 출력한다.


입력 예

3
10 5
9 3
10 5

출력 예

9
13
18

입력 예

2
100 1
1 100

출력 예

1
2

입력 예

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

출력 예

1000000000
2000000000
3000000000
4000000000
5000000000


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP