Eat Economically

Time limit3sMemory limit1024 MB

Summary

For each i from 1 to N, choose i lunch and i dinner menus from 2N distinct menus to minimize the total price, and print the N minimum totals.

Level: Hard8 of 10
Topics: Sorting, Greedy, Divide and conquer
Solved: No attempts yet

Problem

Ho has arrived in a secret place for her secret business trip. She knows her trip will take at most $N$ days or shorter but doesn't know the exact number of days she'll be there. So, the perfectionist Ho wants to make the daily meal lists for every possible trip length, from 1 day to $N$ days. There is only one food court in this secret place, and it offers exactly $2N$ kinds of menus (by accident). The food court is open only at lunch time and dinner time. The prices of lunch and dinner for the same menu can be different. She eats exactly one menu at lunch and one at dinner each day, and she never eats the same menu twice during the entire trip. She does not mind which menus she eats. The only thing that matters is that the total price of her meals is minimized. Under these conditions, she could write out the meal lists, but writing all $N(N+1)$ menus is hard and tiresome. So, instead of making the meal lists, she calculates the minimized total price for $i$ lunch menus and $i$ dinner menus for each $i$ from 1 to $N$ . You are a big fan of Ho, and your task is to print the $N$ prices she calculated.

Input

The first line contains an integer $N$ . Each of the next $2N$ lines contains two integers $l$ and $d$ , the prices of the menu at lunch and at dinner.

Output

Print $N$ lines. The $i$ -th line ( $1 \leq i \leq N$ ) should contain an integer denoting the minimized total price for $i$ lunch menus and $i$ dinner menus.

Constraints

$1 \leq N \leq 250\,000$ and $1 \leq l, d \leq 10^9$ .

Examples3

Example 1
Input
```
1
4 9
5 3
```
Expected output
```
7
```
Example 2
Input
```
2
1 6
2 4
5 3
3 1
```
Expected output
```
2
7
```

Example 3

Input

Expected output