P2006 Zhao Shenniu's Game

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.

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

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