D. 卖家 Bob

去年，Bob 靠卖内存条赚了钱。在他工作的 \(n\) 天里，每天都会发生以下两种情况之一：

有顾客来找 Bob，想买一根容量为 \(2^x\) MB 的内存条。如果 Bob 手上有这样的内存条，他就卖了，赚了 \(2^x\) berllar 币。
Bob 在某个编程比赛中获奖，得到了一个容量为 \(2^x\) MB 的内存条作为奖品。Bob可以选择把这根内存条送给朋友，或者自己留下。

Bob 从不同时拥有超过一根内存条，因为他怕搞混容量，误导顾客。还有一点，每种容量的内存条最多只有一个顾客想买。现在，知道了过去 \(n\) 天里所有顾客的需求和 Bob 赢得的奖品内存条，Bob 想知道，如果他事先知道所有情况，怎么做才能赚最多的钱。

输入格式

第一行输入一个数字 \(n\)（\(1 ≤ n ≤ 5000\)），表示 Bob 工作的天数。接下来 \(n\) 行描述每天的情况。sell x 表示当天有顾客来买容量为 \(2^x\) MB 的内存条（\(0 ≤ x ≤ 2000\)）。保证每种容量的内存条最多只有一条 sell x 记录。win x 表示当天 Bob 赢得了一个容量为 \(2^x\) MB 的内存条（\(0 ≤ x ≤ 2000\)）。

输出格式

输出 Bob 能赚到的最大 berllar 币数，假设他事先知道所有事件。别忘了，Bob 一次最多只能留一根内存条哦。

样例

输入 1

7
win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10

输出 1

输入 2

3
win 5
sell 6
sell 4

输出 2

本页作者： CB-X2-Jun

若未特别说明，本站使用 SATA 与 CC BY-NC-SA 4.0。