Konjac Jellies

Problem Description

A row of konjac jellies sits on the shelf of a convenience store, dazzling the picky shopper...

Each jelly has a price $w$ and a taste value $t$. The picky shopper has a shopping basket, and when selecting konjac jellies he may perform the following operations:

• Operation $1$: put a jelly with price $w$ and taste $t$ into the basket.
• Operation $2$: take out the cheapest jelly in the basket.
• Operation $3$: take out the worst-tasting jelly in the basket ($t$ the smaller, the worse the taste).

The picky shopper dislikes duplicates: when an operation $1$ has a price or a taste already present in the basket, he immediately puts the jelly back on the shelf.

After $n$ operations, the picky shopper has decided which jellies to buy. Please help him compute the total price of the jellies left in the basket.

Input Format

The first line contains a positive integer $n$, the number of operations.

Lines $2$ to $n+1$ each contain one or three integers, representing $op$, $w$, $t$ respectively.

$w$ and $t$ are present if and only if $op = 1$.

Output Format

Output one integer, the total price of the jellies in the basket.

Sample Input

6
1 1 1
1 2 5
2
1 3 3
3
1 5 2

Sample Output

7

Constraints

For all data, $1 \le n \le 10^5$, $1 \le w, t \le 10^6$, and the input is guaranteed to be valid.