== include(page="template/taskheader" task_id="expectedgoals") ==

Poveste şi cerinţă...

Lately, Stefan has been interested in studying football statistics and one day, he discovered a new metric called "expected goals" $xG$. In order to see how can $xG$ affect football games, he gathered data from various football games and now he needs your help to process the data he got.
 
In order to start the research, he told you that there will be $q$ events during the football season, and the events are of two types:
 
$1$ $k$: His database gets a scoring chance worth $k$ $xG$. Since $xG$ is usually represented as a real number, he gave you its value multiplied by $10^6$, so that $k$ is an integer. Therefore, $k$ can be between $1$ and $10^6$, on a probability scale from $10^-6$ to $1$ (the probability can never be equal to $0$).
 
$2$ $p$: He wants to find the smallest amount of $xG$ needed in order for a team to score $p$ goals, if we assume that all the scoring chances have been converted into goals.
 
The database became really big and Stefan got into trouble, so it's up to you to help him!

h2. Date de intrare

Fişierul de intrare $expectedgoals.in$ ...

The first line of the input file $expectedgoals.in$ contains $q$, the number of queries $1 ≤ q ≤ 10^6$.
 
The next $q$ lines of the input contain two integers $type$ and $k$ $1 ≤ type ≤ 2$, $1 ≤ k ≤ 10^6$, $1 ≤ p ≤ 10^6$; For type $2$, $p$ is guaranteed to be at most equal to the number of events of type $1$ which happened already before the current query.

h2. Date de ieşire

În fişierul de ieşire $expectedgoals.out$ ...

The output file $expectedgoals.out$ will contain on each line, the answers for the queries of type $2$, in the order from the input.

h2. Restricţii

* $... ≤ ... ≤ ...$

* For tests worth $30$ points, $1 ≤ q ≤ 2 * 10^3$, $1 ≤ k ≤ 100$.
* For tests worth $30$ more points, $1 ≤ k ≤ 100$.

h2. Exemplu
table(example). |_. expectedgoals.in |_. expectedgoals.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10
1 20
1 8
1 14
1 11
2 3
1 5
1 8
1 11
2 5
2 7
| 33
43
77

|
h3. Explicaţie

...

After the first $5$ queries, the array is $20, 8, 14, 11$. The smallest amount of $xG$ we can get from $5$ values is obtained by taking $8$, $11$ and $14$ and the $xG$ sum is $33$.
 
After the first $9$ queries, the array is $20, 8, 14, 11, 5, 8, 11$. The smallest amount of $xG$ we can get from $5$ values is obtained by taking $8$, $11$, $5$, $8$ and $11$ and the $xG$ sum is $43$.
 
After the first $10$ queries, the array is $20, 8, 14, 11, 5, 8, 11$ and we have to take every single value, and the sum is $77$.

== include(page="template/taskfooter" task_id="expectedgoals") ==