Title Description

You have traveled to a continent of swords and magic and received a prophecy. You were informed of several events settled in sequence. These events are divided into two categories: campaign events (CASE) and time travel events (END). You can choose whether to participate in battle events, and after participating, you will receive a certain amount of money. Each END event requires participation in at least a certain number of campaign events. Especially, if the END event meets the requirements, it will be forced to occur. Once an END event occurs, it will be forced to travel back and cannot participate in the following battles. You hope to have enough fun in mainland China, so you demand that only the last END event will occur, and you hope to earn the most money.

Input format

The first line is a number $N$, indicating how many lines the input file has.

Next, each line is separated by a space between a character and an integer. The character 'c' represents a campaign event, and the following integer represents how much money will be earned from this RP increase; The character 'e' represents the event of crossing back, and the following integer represents the minimum number of battles to participate in. The last event guarantee is the END event.

Output format

The first line is an integer that represents the maximum amount of money.

If not possible, output $-1$.

Example

5
c 10
c 12
e 2
c 1
e 2
``````output1
13

Data scale and agreement

The data of $30 \%$satisfies $N \le 20$;

The data of $60 \%$satisfies $N \le1000$;

$100 \%$data satisfies $N \le 200000$;

The bounty for each RP increase event shall not exceed $10000$.

The requirement for crossing events does not exceed $200000$.