레스토랑 주문 최소 비용

한 레스토랑에는 N가지 음식이 있다. 한 손님은 서로 다른 음식을 원하는 개수만큼 주문할 수 있으며, 같은 음식을 두 번 이상 주문할 수 없다.

주문에서는 어떤 음식을 첫 번째로 고르는지가 중요하다. 음식 i는 첫 번째로 주문하면 A_i원, 첫 번째가 아니면 B_i원이다.

음식을 정확히 1개, 2개, ..., N개 주문할 때 필요한 최소 비용을 각각 구하라.

첫째 줄에 음식의 개수 N이 주어진다. (2 <= N <= 500,000)

다음 N개의 줄에 각 음식의 가격 A_i와 B_i가 주어진다. (0 <= A_i, B_i <= 1,000,000,000)

총 N개의 줄을 출력한다. k번째 줄에는 음식을 정확히 k개 주문할 때 필요한 최소 비용을 출력한다.