F. The Heist of the Century
time limit per test
0.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Please note the low time limit. Solutions in Python should be submitted under PyPy 3-64.

Welcome, aspiring thieves! Today, you are tasked with robbing room number $$$25$$$. In your gear, we will only provide you with a small backpack, as there isn't much valuable stuff at the destination. However, even such items can be useful for the Headquarters! Yes, the backpack is a bit old, but it can hold a lot of useful and necessary items for the Headquarters! Periodically, you will receive queries from the base. The queries can be as follows:

  1. + x. You are instructed to pick up and put a chocopie worth $$$x$$$ burleys into the backpack.
  2. - x. You urgently need to throw out any chocopie worth $$$x$$$ burleys from the backpack to avoid being caught by Kirill Evgenievich. The Headquarters closely monitors the contents of your backpack, so you must always throw out a chocopie that is present in the backpack.
  3. ? W. Vladimir Evgenievich is nearby, and he will consider the backpack suspicious if the total value of the chocopies in it exceeds $$$W$$$. The base wants to know the maximum value of chocopies that can hypothetically be left in the backpack after throwing out some chocopies. Chocopies are not thrown out after the query is made.
During the process, you cannot keep the stolen goods, so if you get caught, you won't easily get rid of the traces of the crime. We suggest you practice robbing the room in this task so that you don't mess up on the main mission. Good luck, the Headquarters is counting on you!
Input

The first line contains two numbers $$$q$$$ and $$$g$$$ ($$$1 \le q \le 10^4$$$, $$$0 \le g \le 10$$$) — the number of queries from the base and the test group number.

In the following $$$q$$$ lines, a queries is entered in the corresponding format:

  1. + x. $$$(1 \le x \le 10^4)$$$
  2. - x. $$$(1 \le x \le 10^4)$$$. It is guaranteed that $$$x$$$ is already in your backpack.
  3. ? W. $$$(0 \le W \le 10^4)$$$
Output

For each query of type ? from the base, output the maximum value of the chocopies that can be left.

Scoring
№Additional constraintsPointsRequired groupComment
$$$q$$$$$$W$$$
$$$0$$$————Tests from the statement
$$$1$$$$$$q \le 16$$$—$$$10$$$$$$0$$$—
$$$2$$$$$$q \le 32$$$—$$$12$$$$$$0-1$$$—
$$$3$$$$$$q \le 300$$$$$$W \le 200$$$$$$7$$$——
$$$4$$$——$$$7$$$—All queries of type $$$1$$$ and $$$2$$$ come before all queries of type $$$3$$$
$$$5$$$——$$$8$$$$$$4$$$All queries of type $$$2$$$ come before all queries of type $$$3$$$
$$$6$$$——$$$11$$$$$$4$$$All queries of type $$$1$$$ come before all queries of type $$$3$$$
$$$7$$$——$$$9$$$—All values for removal come in reverse order of addition
$$$8$$$——$$$12$$$—All values for removal come in the same order as addition
$$$9$$$$$$q \le 2000$$$—$$$8$$$$$$0-3$$$—
$$$10$$$——$$$16$$$$$$0-9$$$—
Examples
Input
10 0
+ 5
+ 6
+ 1
+ 2
- 2
? 12
? 7
+ 2
- 5
? 10
Output
12
7
9
Input
14 0
+ 1
+ 1
+ 1
? 5
? 4
? 3
? 2
+ 2
+ 2
? 100
- 1
? 100
- 1
? 100
Output
3
3
3
2
7
6
5