Description

This is an adapted problem.

On Mount Fajiu, there are many zhe trees. There is a bird whose form resembles a crow, with a patterned head, a white beak, and red feet. Its name is Jingwei, and its call is like its name. She was the young daughter of the Flame Emperor, named Nüwa. Nüwa went to play in the Eastern Sea, drowned, and did not return, so she became Jingwei. She often carries wood and stones from the Western Mountains to fill up the Eastern Sea. — Classic of Mountains and Seas

Jingwei is finally about to fill up the Eastern Sea—only a small area remains. At the same time, there are not many pieces of wood and stone left on the Western Mountains. Can Jingwei finish the task?

In fact, the remaining unfilled area of the Eastern Sea requires at least a total volume of $v$ worth of wood and stones to be filled. There are $n$ pieces left on the Western Mountains. For the $i$-th piece, its volume and the stamina required to carry it to the Eastern Sea are $k_i$ and $m_i$, respectively. Jingwei is very tired after working for so long, and her remaining stamina is $c$.

Input Format

The first line contains three integers: $v$, $n$, $c$.

Lines $2$ through $n+1$ each contain two integers $k_i$ and $m_i$, the volume of the $i$-th piece and the stamina required to carry it to the Eastern Sea.

Output Format

Output a single line. If Jingwei can fill the Eastern Sea, output the maximum stamina she can have left after filling it. Otherwise, output Impossible.

100 2 10
50 5
50 5

0

10 2 1
50 5
10 2

Impossible

Hint

Constraints and Conventions

• For $20\%$ of the testdata, $0 < n \le 50$.
• For $50\%$ of the testdata, $0 < n \le 1000$.
• For $100\%$ of the testdata, $0 < n \le 10^4$, all input numbers are in $[0, 10^4]$, and the final answer is not greater than $c$.

Translated by ChatGPT 5