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

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

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

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

모든 친구가 음료수를 싫어한다면 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개 살때까지의 각각의 최소 비용을 한줄에 하나씩 출력한다.