去年鲍勃靠卖记忆棒赚了钱。在他工作的 n 天中,每天都会发生以下两件事之一:
- 一位顾客来找 Bob,要求卖给他一个 2x MB 的记忆棒。如果鲍勃有这样一根棍子,他就会卖掉它并得到 2x 贝拉尔。
- Bob 赢得了一些编程比赛并获得了 2x MB 记忆棒作为奖品。鲍勃可以选择是否将这个记忆棒赠送给他的一位朋友,或者保留它。
鲍勃只保留一根记忆棒,因为他担心混淆它们的容量,无意中欺骗顾客。还已知的是,对于每个记忆棒容量,最多有一个顾客想要购买该记忆棒。现在,了解了所有客户的需求以及过去 n 天在编程比赛中获得的所有奖品,Bob 想知道,如果他表现最佳,他可以赚多少钱。
输入
第一输入行包含数字 n (1 ≤ n ≤ 5000) — Bob 的工作日数。接下来的 n 行包含了这些日子的描述。 Line sell x 代表客户来 Bob 购买 2x MB 记忆棒的一天 (0 ≤ x ≤ 2000)。保证对于每个 x,卖出 x 的行数不超过一条。 win x 行代表 Bob 赢得 2x MB 记忆棒的一天 (0 ≤ x ≤ 2000)。
输出
输出鲍勃在贝拉尔中可能获得的最大收入,如果他事先知道所有事件,他将获得该收入。请不要忘记,鲍勃一次只能保留一根记忆棒。
示例
输入 #1
7 win 10 win 5 win 3 sell 5 sell 3 win 10 sell 10
输出 #1
1056
输入 #2
3 win 5 sell 6 sell 4
输出 #2
0