Монокарп собирает армию в компьютерной игре, чтобы сразиться с драконом.
Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.
Перед началом боя Монокарп раздает артефакты героям так, чтобы каждый герой получил не более одного артефакта.
Бой состоит из раундов, которые проходят следующим образом:
- сначала дракон наносит каждому герою урон, равный \(\frac{1}{a + b}\) (вещественное число без округления), где \(a\) — количество живых героев, а \(b\) — количество активных артефактов;
- после этого все герои со здоровьем \(0\) или меньше умирают;
- наконец, некоторые артефакты деактивируются. Артефакт с прочностью \(x\) деактивируется, когда происходит одно из следующего: герой, держащий артефакт, либо умирает, либо получает суммарно \(x\) урона (от начала боя). Если артефакт не выдан ни одному из героев, он считается неактивным с самого начала битвы.
Бой заканчивается, если в живых не осталось ни одного героя.
Изначально армия пуста. Приходит \(q\) запросов: добавить в армию героя со здоровьем \(x\) или артефакт с прочностью \(y\). После каждого запроса найдите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.
Выходные данные
Выведите \(q\) целых чисел. После каждого запроса выведите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.