Codeforces Beta Round 18 (Див. 2) |
---|
Закончено |
В прошлом году Вася подрабатывал продажей компьютерных флешек. В каждый из n дней его работы происходило одно из двух:
Вася никогда не хранил у себя больше одной флешки, так как боялся перепутать их объемы и случайно кого-нибудь обмануть. Также известно, что для каждого объема флешки было не более одного покупателя, желающего купить такую флешку. Сейчас, зная все запросы покупателей и все призы на олимпиадах по программированию за прошедшие 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
Название |
---|