1# 胖哥购物(shopping.cpp/c/pas)

1# 胖哥购物(shopping.cpp/c/pas)

Description

今天,胖哥在淘宝上购物。刚开始,胖哥的手上没有任何的优惠券。已知在购物过程中,胖哥将会按顺序遇到 n 个事件:
1 x:购买一个价值为 x 的商品。当发生这种事时,胖哥最多只能使用一张面值小于 x的优惠券去减免。若手中没有优惠券,则全额购买。
2 x:得到一张 x 元的优惠券。
胖哥想知道,在最优的策略下,完成今天的购物最少要花掉多少钱。

Format

Input

共 n+1 行,第一行包含一个整数 n,表示事件的个数。
接下来 n 行,每行两个正整数 type x。若 type=1,表示是事件 1,若 type=2,表示是事件 2。

Output

输出共一行,包含一个整数,表示完成今天的购物最少要花掉多少钱。

Sample 1

Input

10
2 4
1 6
1 6
2 4
1 1
2 2
2 3
2 3
1 3
1 6

Output

12

Limitation

1s, 256MiB for each test case.
【数据说明】
对于 30%的数据,1≤n≤10。
对于 60%的数据,1≤n≤1000。
对于 100%的数据,1≤n≤100000。
对于 100%的数据,1≤x≤100000。

Source

2018年泉州复赛模拟提高组 day3t1