Magic Tower Online

In the game Magic Tower Online published by BitGame Company, players control a warrior to battle monsters in a magical tower. At the beginning of the game, there are no monsters in the tower. Then, q events occur one by one. Each event is one of the following three types:

• + x y z a b: A new version of the game is released and a new monster is added. If this is the first added monster then its id is 1; otherwise, its id is the last added monster’s id + 1. The monster is on layer x of the tower, has level y, and difficulty z. To defeat this monster, the warrior must spend a hit points; after a successful battle, the warrior immediately obtains and uses a potion that recovers b hit points.
• - k: A new version is released that removes the monster with id k from the tower due to balance issues. Note: The removed monster still keeps its id; future monsters will not reuse ids of removed monsters.
• ? g l d: A query. A player is considering to defeat all monsters in the first g layers that have level at most l and difficulty at most d. The player can choose an arbitrary order to fight the selected monsters. Climbing to a new layer does not require defeating every monster on the current layer, and during the fighting process no other monsters interfere. Your task is to help the player calculate the minimum initial hit points needed such that the warrior never has negative hit points at any moment. (If at any moment the warrior’s hit points become negative, the game is over — you must avoid that situation.)

Note: Each query is only a thought experiment and does not actually remove or kill any monster.

The optimal strategy is to choose the order in which to fight the monsters to minimize the needed initial hit points. Formally, you are given a set of monsters. For each monster with required cost a and potion gain b, fighting it changes the warrior’s hit points by
$$ -a \quad (\text{before the fight}) \quad \text{and then} \quad +b \quad (\text{immediately after a win}). $$
A valid order is one in which, if the warrior starts with H hit points, his hit points never drop below 0 at any moment. It can be shown that one optimal strategy is to partition the monsters into two groups:
Group 1: monsters with \( a \le b \). Sort these in increasing order of \( a \).
Group 2: monsters with \( a > b \). Sort these in decreasing order of \( b \).
Then simulate the battles in that order. If at any battle the current hit points is less than the required cost \( a \), you must have had an extra boost in the initial hit points. The answer is the sum of all such extra boosts plus 1 (since even with no monsters, 1 hit point is required).

Your program needs to process all the events in order and answer every query.

inputFormat

The first line contains a single integer q (the number of events). Each of the following q lines contains an event in one of the three formats described above.

The parameters are defined as follows:

• x: layer of the monster.
• y: level of the monster.
• z: difficulty of the monster.
• a: hit points cost to kill the monster.
• b: hit points recovered from the potion after killing the monster.
• k: monster id.
• g, l, d: query parameters for layer, level and difficulty respectively.

outputFormat

For each query event (a line starting with '?'), output a single line with the minimum initial hit points required for the warrior to clear the selected monsters without his hit points ever becoming negative.

sample

1
? 10 100 100

1