В прошлом году Вася подрабатывал продажей компьютерных флешек. В каждый из n дней его работы происходило одно из двух:
- К Васе приходил покупатель и спрашивал флешку на 2x мегабайт. Если у Васи была такая флешка, он продавал ее и получал 2x бурлей.
- Вася выигрывал какую-нибудь олимпиаду по программированию и получал в качестве приза флешку на 2x мегабайт. При этом он мог выбрать, подарить ли ему эту флешку кому-то из друзей, или оставить ее себе.
Вася никогда не хранил у себя больше одной флешки, так как боялся перепутать их объемы и случайно кого-нибудь обмануть. Также известно, что для каждого объема флешки было не более одного покупателя, желающего купить такую флешку. Сейчас, зная все запросы покупателей и все призы на олимпиадах по программированию за прошедшие n дней, Васе интересно, сколько денег он мог бы заработать, если бы действовал оптимально.
Выходные данные
Выведите наибольший возможный заработок Васи в бурлях, если бы он заранее знал все события. Не забудьте, что Вася не может хранить у себя одновременно больше одной флешки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10
|
1056
|
|
2
|
3
win 5
sell 6
sell 4
|
0
|