Skill Selection for Boss Defeat in DNF

Zhao ShenNiu possesses k mana points and has m skills available. The i^th skill requires a_i mana and inflicts b_i damage. The boss has n health points. Since Zhao ShenNiu can only use one type of skill in a game (but that skill may be used an unlimited number of times), determine which skill to use so that the boss is defeated.

Mathematically, for each skill i (1-indexed), find if there exists a positive integer x such that

$$x \times a_i \le k \quad \text{and} \quad x \times b_i \ge n. $$

If multiple skills can defeat the boss, output the one with the smallest index. If no skill can defeat the boss under the mana constraint, output -1.

inputFormat

The first line contains three integers k, m, and n representing the total mana, number of skills, and the boss's health respectively. Each of the following m lines contains two integers a_i and b_i, denoting the mana cost and damage of the i^th skill.

outputFormat

Output a single line containing the index (1-indexed) of the skill that can defeat the boss. If no skill meets the requirement, output -1.

sample

10 3 15
3 5
4 7
6 9

1

</p>