便利蜂的货架上摆了一排蒟蒻果冻,搞得鶸尛鱻眼花缭乱......
对于每个果冻,都有一个价格 $w$ 和口感 $t$。鶸尛鱻有一个购物篮子,在挑选蒟蒻果冻的时候,他有以下几种操作:
- 操作 $1$:把一个价格为 $w$,口感为 $t$ 的果冻放入篮子。
- 操作 $2$:拿出篮子中 最为廉价 的果冻。
- 操作 $3$:拿出篮子中 口感最差 的果冻。($t$ 越小,口感越差)
鶸尛鱻不喜欢重复,当操作 $1$ 的 价格或口感 与篮中已有果冻重复时,他会立刻将其放回货架。
经过 $n$ 次操作后,鶸尛鱻确定了要购买的若干果冻,请你帮他求出篮子里果冻的总价格。
输入格式
第 $1$ 行一个正整数 $n$,代表操作次数。
第 $2$ 行至第 $(n+1)$ 行,每行 一个或三个 整数,分别表示 $op$,$w$,$t$。
$w$ 和 $t$ 当且仅当 $op = 1$ 时存在。
输出格式
输出一个整数,表示篮子里果冻的总价格。
样例输入
6
1 1 1
1 2 5
2
1 3 3
3
1 5 2
样例输出
7
数据规模
所有数据保证 $1 \le n \le 10^5$,$1 \le w, t \le 10^6$,且保证输入合法。