Problem Description

In DNF, Zhao Shenniu has a Creator with a total of $k$ mana points. He has $m$ skills, each costing $a_i$ mana points and causing $b_i$ damage. The boss's health is $n$. Please determine which skill he should use to kill the boss.

Of course, Zhao Shenniu is not very skilled, so he only uses one skill per game, but each skill can be used infinitely many times.

Input Format

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

The next $m$ lines, each containing two integers, represent the mana cost $a_i$ and the damage $b_i$ of the skill on the $(i + 1)$th line.

Output Format

Output a single line, which is the sequence number of the skill that can kill the boss. If there are multiple, output them in ascending order separated by a space. If no skill can kill the boss, output -1.

Sample Input and Output

Sample Input #1

100 3 5000
20 1000
90 1
110 10000

Sample Output #1

1

Sample Input #2

50 4 10
60 100
70 1000
80 1000
90 0

Sample Output #2

-1

Notes

Data Size and Constraints

For all test cases, the following constraints apply:

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

见题面 Input 部分

见题面 Output 部分