P6494 [COCI 2016/2017 #2] Go

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.

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$.

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.

#### 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T1 Go_**。 Translated by ChatGPT 5