Fişierul intrare/ieşire: | expectedgoals.in, expectedgoals.out | Sursă | IIOT 2021-22 Runda 2 |

Autor | Stefan Dascalescu | Adăugată de | Stefan Dascalescu •stefdascalescu |

Timp execuţie pe test | 2.5 sec | Limită de memorie | 65536 kbytes |

Scorul tău | N/A | Dificultate | N/A |

Vezi solutiile trimise | Statistici

# Goal Statistics

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

`106`, 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!

## Date de intrare

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 ≤ 106`. 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.

## Date de ieşire

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

## Restricţii

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

## Exemplu

expectedgoals.in | expectedgoals.out |
---|---|

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

### 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`.