After many twists and turns, Hobanwoo has finally arrived in front of the starting village. However, the stairs leading to the village on the cliff have been destroyed by monsters, so he has decided to build stairs using logs.

He builds the stairs by placing logs vertically side by side. Occasionally, monsters use magic with power $m$, which targets the current longest log of length $k$ among all logs placed so far. Any log with a length of at least $\max(k-m, 0)$ has its length reduced to $\max(k-m, 0)$.

You are given $N$ queries:

1 a : Hobanwoo places a log of length $a$ next to the stairs. 2 m : Monsters use magic of power $m$ on the stairs.

The logs Hobanwoo adds are always longer than any log previously added by a type 1 query.

Calculate the sum of the lengths of all logs in the completed stairs after $N$ queries.

Input

The first line contains the number of queries $N$. Starting from the second line, $N$ lines follow, each containing two positive integers $x$ and $y$ separated by a space. If $x$ is 1, Hobanwoo has placed a log of length $y$ next to the stairs; the new log is always longer than any log previously added by a type 1 query. If $x$ is 2, the monsters have used magic of power $y$ on the stairs; this query can occur even if there are no logs on the stairs. ($1 \le N \le 500\,000$) ($1 \le x \le 2$) ($1 \le y \le 10^9$)

Output

Output the sum of the lengths of all logs in the completed stairs after $N$ queries.

Examples

Input 1

1
1 1000000000

Output 1

1000000000

Input 2

1
2 1000000000

Output 2

0