Description

In the game Evolve! Pokemon, Mirko has $n$ Pokemon. To complete their evolutions, Mirko has prepared $m_i$ candies for the $i$-th Pokemon.

Each time he evolves the $i$-th Pokemon, he must spend $k_i$ candies prepared for it. After the evolution is completed, Mirko will receive $2$ candies of the same type as a reward. Note that each Pokemon can only use its own corresponding candies to evolve.

Mirko wants to know how many evolutions he can complete in total, and which Pokemon can be evolved the most times. If the Pokemon with the maximum number of evolutions is not unique, choose the one that appears earlier in the input.

Input Format

The first line contains an integer $n$.

The next $2 \times n$ lines:

• Line $2 \times i$ contains a string, the name of Mirko's $i$-th Pokemon.

• Line $2 \times i + 1$ contains two integers $k_i, m_i$.

Output Format

The first line contains an integer, the total number of evolutions Mirko can complete.

The second line contains a string, the name of the Pokemon that can be evolved the most times.

4
Caterpie
12 33
Weedle
12 42
Pidgey
12 47
Rattata
25 71 

14
Weedle 

7
Bulbasaur
25 74
Ivysaur
100 83
Charmander
25 116
Charmeleon
100 32
Squirtle
25 1
Wartortle
100 173
Pikachu
50 154 

11
Charmander

Hint

Sample 1 Explanation

For Weedle's first evolution, Mirko spends $12$ candies, then receives $2$ candies as a reward. At this time, there are $42 - 12 + 2 = 32$ candies left for Weedle to evolve. In this way, Mirko can evolve Weedle a total of $4$ times.

Similarly, Mirko can evolve Caterpies $3$ times, Pidgeys $4$ times, and Rattatas $3$ times. In total, he can complete $14$ evolutions, which is the first part of the answer.

Among them, Weedle and Pidgeys have the most evolutions, both $4$ times. Since Weedle appears earlier than Pidgeys in the input, Weedle is used as the second part of the answer.

Constraints

For $100\%$ of the testdata, $1 \le n \le 70$, $12 \le k_i \le 400$, $1 \le m_i \le 10^4$.

All strings have length at most $20$, and contain only uppercase and lowercase letters.

Notes

This problem is translated from COCI2016-2017 CONTEST #2 T1 Go。

Translated by ChatGPT 5