Козак Вус та міньйони

Бути міньйоном — це звісно ж круто, але Козак Вус сильніший за них...

У розпорядженні у Козака Вуса є $n$ міньйонів, пронумерованих цілими числами від $1$ до $n$. Кожен міньйон характеризується своїми силою та витривалістю. У $i$-го міньйона сила рівна $a_i$, а витривалість рівна $b_i$.

Козак Вух попросив Козака Вуса передати йому в розпорядження загін міньйонів. Припустимо, що Козак Вух попросив передати $k$ міньйонів. Тоді Козак Вус може передати будь-які $k$ міньйонів своєму другу. Ці міньйони можуть мати будь-які номери, не обов'язково послідовні. В кожному загоні має бути один лідер, який вибирається Козаком Вусом.

Герої для кожного загону міньйонів визначили його ціну. Вони вважають, що ціна загону рівна сумі сили лідера та витривалостей всіх інших міньйонів в загоні (якщо такі є). Розміром загону називають кількість міньйонів у ньому.

Припустимо, що є чотири міньйони, у яких:

1. сила $3$, а витривалість $6$,

2. сила $7$, а витривалість $3$,

3. сила $1$, а витривалість $8$,

4. сила $6$, а витривалість $5$.

Якщо Козак Вух просить передати йому загін з $3$ міньйонів, то Козак Вус може, наприклад, вибрати першого, другого та четвертого. Якщо він назначить другого лідером, то ціна загону буде рівна $7$ (сила лідера) $+$ $6$ (витривалість першого) $+$ $5$ (витривалість четвертого) $=18$.

Нехай $f(k)$ — мінімальна ціна загону серед всіх загонів, в яких розмір $k$.

У попередньому прикладі Козаку Вусу для мінімізації ціни краще за все вибрати загін, в якому другий, третій та четвертий міньйони та призначити третього міньйона лідером. Тоді ціна загону рівна $1+3+5=9$. Оскільки немає кращого рішення, то $f(3)=9$.

Тепер Козаки хочуть дізнатись всі можливі значення $f$. Допоможіть Козакам дізнатись значення $f(1),f(2),\dots ,f(n)$.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 2\cdot 10^5)$ — кількість міньйонів у розпорядженні у Козака Вуса.

Кожний з наступних $n$ рядків містить два цілих числа $a_i$ та $b_i$ $(1\le a_i,b_i\le 10^9)$ — значення сили та витривалості міньйона з номером $i$ відповідно.

Вихідні дані

Виведіть $n$ цілих чисел — $f(1),f(2),\dots ,f(n)$.

Приклади

Примітка

Пояснення до першого прикладу:

Щоб утворити загін мінімальної вартості серед всіх загонів розміру $1$, необхідно утворити загін що складається з міньйона з номером $1$.

Щоб утворити загін мінімальної вартості серед всіх загонів розміру $2$, необхідно утворити загін що складається з міньйонів з номерами $1$ та $3$ та вибрати лідером міньйона з номером $1$.

Щоб утворити загін мінімальної вартості серед всіх загонів розміру $3$, необхідно утворити загін що складається з всіх міньйонів та вибрати лідером міньйона з номером $1$.

Оцінювання