D. Продавец Вася
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
128 megabytes
ввод
stdin
вывод
stdout

В прошлом году Вася подрабатывал продажей компьютерных флешек. В каждый из n дней его работы происходило одно из двух:

  • К Васе приходил покупатель и спрашивал флешку на 2x мегабайт. Если у Васи была такая флешка, он продавал ее и получал 2x бурлей.
  • Вася выигрывал какую-нибудь олимпиаду по программированию и получал в качестве приза флешку на 2x мегабайт. При этом он мог выбрать, подарить ли ему эту флешку кому-то из друзей, или оставить ее себе.

Вася никогда не хранил у себя больше одной флешки, так как боялся перепутать их объемы и случайно кого-нибудь обмануть. Также известно, что для каждого объема флешки было не более одного покупателя, желающего купить такую флешку. Сейчас, зная все запросы покупателей и все призы на олимпиадах по программированию за прошедшие n дней, Васе интересно, сколько денег он мог бы заработать, если бы действовал оптимально.

Входные данные

В первой строке входных данных содержится число n (1 ≤ n ≤ 5000) — сколько дней работал Вася. Следующие n строк содержат описание дней. Строка вида sell x описывает день, в который к Васе приходил покупатель за флешкой на 2x мегабайт (0 ≤ x ≤ 2000). Гарантируется, что для каждого x задано не более одной строки вида sell x. Строка вида win x описывает день, в который Вася выиграл флешку на 2x мегабайт (0 ≤ x ≤ 2000).

Выходные данные

Выведите наибольший возможный заработок Васи в бурлях, если бы он заранее знал все события. Не забудьте, что Вася не может хранить у себя одновременно больше одной флешки.

Примеры
Входные данные
7
win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10
Выходные данные
1056
Входные данные
3
win 5
sell 6
sell 4
Выходные данные
0