Description

In DNF, Zhao Shenniu has a "Dizaozhe" character. He has a total of $k$ mana points and there are $m$ skills. Each skill costs $a_i$ mana and deals $b_i$ damage. The boss has $n$ health points. Please determine which skill he should cast to kill the boss.

Of course, Zhao Shenniu is not very skilled; in one game he only uses one skill, but any chosen skill can be cast an unlimited number of times.

Input Format

The first line contains three integers, representing $k, m, n$.

Then follow $m$ lines. The $(i + 1)$-th line contains two integers: the mana cost $a_i$ and the damage $b_i$.

Output Format

Output a single line: the indices of the skills that can kill the boss. If there are multiple, output them in increasing order, separated by a single space. If no skill can kill the boss, output -1.

100 3 5000
20 1000
90 1
110 10000

1

50 4 10
60 100
70 1000
80 1000
90 0

-1

Hint

Constraints

For all test points, it holds that:

• $0 < n, m \le 3 \times 10^4$.
• $0 \le k \le 3 \times 10^4$.
• $0 \le a_i, b_i \le 2147483647$.

Translated by ChatGPT 5