Descrpition

青蛙之神开设了一个酒厂，有很多顾客来买酒。众所周知酒放置时间越长越香醇，一瓶初始价格为 $a_i$ 的酒放置一天后价格会变为 $a_i + 1$ ，放置两天后价格会变为 $a_i + 1 + 2$ ，三天后变为 $a_i + 1 + 2 + 3$ ，以此类推

你需要维护 $n$ 次操作：

操作一： 1 t v 代表青蛙之神的酒厂在第 $t$ 天生产了一瓶初始价格为 $v$ 的酒，并将其存入仓库

操作二： 2 t 代表第 $t$ 天有一个顾客来买酒，此时你可以任选一瓶仓库里的酒卖给他。

请你求出青蛙酒厂最多能获得多少钱

保证输入的 $t$ 严格单调递增且每瓶酒最终都被卖出，每个顾客都能买到酒。

Input

第一行一个正整数 $n$ ，表示操作次数

接下来 $n$ 行每行一个操作，格式如上所示

Output

一行一个数，表示答案

Sample

4
1 1 10
1 2 20
2 3
2 4

37

Limitation

对于 $30\%$ 的数据，$1 \leq n,m \leq 10$ ，且输入的 $t$ 为 $1,2,3,\cdots ,n$

对于 $60\%$ 的数据，$1 \leq n,m \leq 5000$ ，且输入的 $t$ 为 $1,2,3,\cdots ,n$

对于 $100\%$ 的数据， $1 \leq n,m \leq 3 \times 10^5 , 1 \leq a_i \leq 10^6 , 1 \leq t \leq 10^6$