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 가 주어진다.
출력형식
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 |