Minimum Cost for Restaurant Orders

A restaurant sells N different dishes. A customer may order any number of distinct dishes, but cannot order the same dish more than once.

The order matters only for the dish chosen first. For dish i, the price is A_i if it is ordered first and B_i otherwise.

For each k from 1 to N, compute the minimum total cost to order exactly k dishes.

The first line contains N, the number of dishes. (2 <= N <= 500,000)

Each of the next N lines contains two integers A_i and B_i. (0 <= A_i, B_i <= 1,000,000,000)

Print N lines. The k-th line must contain the minimum total cost to order exactly k dishes.