images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
24/04/2024 17:29:08

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1933. Discount

Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Mirko is hungry as a bear, scratch that, programmer and has stumbled upon a local restaurant. The restaurant offers `N` meals and has an interesting pricing policy: each meal `i` has two assigned prices, `A_i` and `B_i`. Mirko pays `A` only for the first ordered meal, while `B` prices apply for all other meals.
Mikro can't decide how many meals to order. In order to make his decision easier, he has asked you to compute, for each `k` between 1 and `N` (inclusive), the minimum total price for `k` ordered meals. Mirko doesn't care which particular meals he orders or in which order he orders them, however he won't order the same meal twice. Order, order, order.
The first line of input contains the positive integer `N` (`2\ ≤\ \ N\ \ ≤\ 500\ 000`), the number of different meals offered by the restaurant.
Each of the following `N` lines contains two positive integers, `A_i` and `B_i` (`1\ ≤\ A_i,\ B_i\ ≤\ 1\ 000\ 000\ 000`), the prices for meal `i` as described above.
Output must consist of `N` lines, where line `k` contains the minimum price for ordering exactly `k` different meals.

Sample Input #1

3
10 5
9 3
10 5

Sample Output #1

9
13
18

Sample Input #2

2
100 1
1 100

Sample Output #2

1
2

Sample Input #3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output #3

1000000000
2000000000
3000000000
4000000000
5000000000
Clarification of the first example:
k = 1: Mirko pays `A_2\ =\ 9` for the starting meal 2.
k = 2: Mirko pays `A_1\ =\ 10` for the starting meal 1, then `B_2\ =\ 3` for meal 2.
k = 3: Mirko pays `A_1\ =\ 10` for the starting meal 1, then `B_2\ =\ 3` for meal 2, and finally `B_3\ =\ 5` for meal 3.
Source: COCI 2012/2013, contest #2
loading