레스토랑 주문 최소 비용
시간 제한2초메모리 제한256 MB
N개의 요리에 대해 첫 주문 가격과 이후 가격이 주어질 때, 각 k에 대해 정확히 k개를 주문하는 최소 비용을 구합니다.
문제
한 레스토랑에는 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개 주문할 때 필요한 최소 비용을 출력한다.