Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

В условии задачи недавно были сделаны правки. Просмотреть изменения.

×
D. Seller Bob

time limit per test

2 secondsmemory limit per test

128 megabytesinput

standard inputoutput

standard outputLast year Bob earned by selling memory sticks. During each of *n* days of his work one of the two following events took place:

- A customer came to Bob and asked to sell him a 2
^{x}MB memory stick. If Bob had such a stick, he sold it and got 2^{x}berllars. - Bob won some programming competition and got a 2
^{x}MB memory stick as a prize. Bob could choose whether to present this memory stick to one of his friends, or keep it.

Bob never kept more than one memory stick, as he feared to mix up their capacities, and deceive a customer unintentionally. It is also known that for each memory stick capacity there was at most one customer, who wanted to buy that memory stick. Now, knowing all the customers' demands and all the prizes won at programming competitions during the last *n* days, Bob wants to know, how much money he could have earned, if he had acted optimally.

Input

The first input line contains number *n* (1 ≤ *n* ≤ 5000) — amount of Bob's working days. The following *n* lines contain the description of the days. Line sell x stands for a day when a customer came to Bob to buy a 2^{x} MB memory stick (0 ≤ *x* ≤ 2000). It's guaranteed that for each *x* there is not more than one line sell x. Line win x stands for a day when Bob won a 2^{x} MB memory stick (0 ≤ *x* ≤ 2000).

Output

Output the maximum possible earnings for Bob in berllars, that he would have had if he had known all the events beforehand. Don't forget, please, that Bob can't keep more than one memory stick at a time.

Examples

Input

7

win 10

win 5

win 3

sell 5

sell 3

win 10

sell 10

Output

1056

Input

3

win 5

sell 6

sell 4

Output

0

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/30/2020 06:13:24 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|