F. Ограбление века
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на низкое ограничение по времени. Решения на языке Python стоит засылать под PyPy 3-64.

Приветствуем начинающих воров! Сегодня вам предстоит ограбить кабинет номер $$$25$$$. В снаряжении мы вам дадим лишь небольшой рюкзак, потому что ценного в месте назначения не сильно много. Однако даже такие вещи могут пригодиться Штабу! Да, рюкзак, конечно, староват, но может вместить много полезного и нужного Штабу! Периодически вам будут поступать запросы от базы. Запросы могут быть таковыми:

  1. + x. Вам велено подобрать и положить в рюкзак чокопай ценностью $$$x$$$ бурлей.
  2. - x. Срочно нужно выкинуть из рюкзака любой чокопай ценностью $$$x$$$ бурлей, чтобы не попасться Кириллу Евгеньевичу. Штаб тщательно следит за наполнением вашего рюкзака, поэтому всегда нужно выкинуть чокопай, который присутствует в рюкзаке.
  3. ? W. Владимир Евгеньевич близко, и он будет считать рюкзак подозрительным, если суммарно чокопаи в нём стоят больше $$$W$$$. База хочет узнать, какую максимальную стоимость чокопаев гипотетически можно оставить в рюкзаке, выкинув некоторые чокопаи. Чокопаи после запроса не выкидываются.
В процессе есть награбленное нельзя, поэтому если вас поймают, от следов преступления вы так легко не избавитесь. Предлагаем потренироваться в ограблении кабинета в данной задаче, чтобы на основной миссии вы не оплошали. Удачи, Штаб рассчитывает на вас!
Входные данные

В первой строке вводятся два числа $$$q$$$ и $$$g$$$ ($$$1 \le q \le 10^4$$$, $$$0 \le g \le 10$$$) — количество запросов от базы и номер группы тестов.

В следующих $$$q$$$ строках вводится запрос в соответствующем формате:

  1. + x. $$$(1 \le x \le 10^4)$$$
  2. - x. $$$(1 \le x \le 10^4)$$$. Гарантируется, что $$$x$$$ уже есть в вашем рюкзаке.
  3. ? W. $$$(0 \le W \le 10^4)$$$
Выходные данные

Для каждого запроса типа ? от базы выведите максимальную стоимость слитков, которую можно оставить.

Система оценки
№Доп. ограниченияБаллыНеобх. группыКомментарий
$$$q$$$$$$W$$$
$$$0$$$————Тесты из условия
$$$1$$$$$$q \le 16$$$—$$$10$$$$$$0$$$—
$$$2$$$$$$q \le 32$$$—$$$12$$$$$$0-1$$$—
$$$3$$$$$$q \le 300$$$$$$W \le 200$$$$$$7$$$——
$$$4$$$——$$$7$$$—Все запросы типа $$$1$$$ и $$$2$$$ идут до всех запросов типа $$$3$$$
$$$5$$$——$$$8$$$$$$4$$$Все запросы типа $$$2$$$ идут до всех запросов типа $$$3$$$
$$$6$$$——$$$11$$$$$$4$$$Все запросы типа $$$1$$$ идут до всех запросов типа $$$3$$$
$$$7$$$——$$$9$$$—Все ценности на удаление идут в обратном порядке, что на добавление
$$$8$$$——$$$12$$$—Все ценности на удаление идут в том же порядке, что и на добавление
$$$9$$$$$$q \le 2000$$$—$$$8$$$$$$0-3$$$—
$$$10$$$——$$$16$$$$$$0-9$$$—
Примеры
Входные данные
10 0
+ 5
+ 6
+ 1
+ 2
- 2
? 12
? 7
+ 2
- 5
? 10
Выходные данные
12
7
9
Входные данные
14 0
+ 1
+ 1
+ 1
? 5
? 4
? 3
? 2
+ 2
+ 2
? 100
- 1
? 100
- 1
? 100
Выходные данные
3
3
3
2
7
6
5