Монокарп собирает армию в компьютерной игре, чтобы сразиться с драконом.
Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.
Перед началом боя Монокарп раздает артефакты героям так, чтобы каждый герой получил не более одного артефакта.
Бой состоит из раундов, которые проходят следующим образом:
- сначала дракон наносит каждому герою урон, равный \(\frac{1}{a + b}\) (вещественное число без округления), где \(a\) — количество живых героев, а \(b\) — количество активных артефактов;
- после этого все герои со здоровьем \(0\) или меньше умирают;
- наконец, некоторые артефакты деактивируются. Артефакт с прочностью \(x\) деактивируется, когда происходит одно из следующего: герой, держащий артефакт, либо умирает, либо получает суммарно \(x\) урона (от начала боя). Если артефакт не выдан ни одному из героев, он считается неактивным с самого начала битвы.
Бой заканчивается, если в живых не осталось ни одного героя.
Изначально армия пуста. Приходит \(q\) запросов: добавить в армию героя со здоровьем \(x\) или артефакт с прочностью \(y\). После каждого запроса найдите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.
Выходные данные
Выведите \(q\) целых чисел. После каждого запроса выведите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.
Примечание
Рассмотрим первый пример.
- Добавляется артефакт с прочностью \(5\). Так как героев пока нет, бой сразу же заканчивается.
- Добавляется герой со здоровьем \(4\). Монокарп может дать ему артефакт с прочностью \(5\). Сначала идут раунды, в которых герою наносится \(\frac{1}{1 + 1} = \frac{1}{2}\) урона. Через \(8\) таких раундов суммарно будет нанесено \(4\) урона, и герой умрет, а артефакт деактивируется. Больше в живых нет героев, так что бой заканчивается за \(8\) раундов.
- Добавляется герой со здоровьем \(10\). Пусть теперь артефакт с прочностью \(5\) будет у этого героя. Тогда за первые \(12\) раундов героям будет нанесено \(12 \cdot \frac{1}{2 + 1} = 4\) урона, и первый герой умрет. У второго героя осталось \(6\) здоровья, а у артефакта \(1\) прочности. Теперь урон равен \(\frac{1}{2}\), поэтому еще за \(2\) раунда артефакт деактивируется. У второго героя осталось \(5\) здоровья. За еще \(5\) раундов умрет второй герой. Поэтому ответ равен \(12 + 2 + 5 = 19\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 5
1 4
1 10
|
0
8
19
|
|
2
|
10
1 9
1 6
2 4
1 8
1 3
2 10
1 3
1 6
1 10
2 6
|
9
15
19
27
30
39
42
48
59
65
|