Dragon Slayer Strategy

In an alternate world, young \(X\) finds himself in a fantasy realm. The king orders him to recruit warriors to kill the evil dragon and rescue the princess.

The dragon has an attack value \(\text{ATK}\) and health \(\text{HP}\). Likewise, each warrior has an attack \(A_i\) and health \(H_i\). The battle is turn‐based: in each round, the warrior deals damage to the dragon and the dragon simultaneously damages the warrior. Specifically, during a round, the dragon's health is reduced by the warrior's attack and the warrior's health is reduced by \(\text{ATK}\) of the dragon.

If after a round the dragon's health is \(\le 0\), the dragon dies. Otherwise, if the warrior's health is \(\le 0\), the warrior is defeated and a new warrior immediately replaces him. However, there's a twist: due to a special tactic, the damage inflicted by the second warrior is doubled, the third warrior's damage is tripled, and so on. In other words, if a warrior is the \(k\)-th to fight, each of his attacks deals \(k \times A_i\) damage.

Your task is to determine the minimum number of warriors required (selected from a pool of \(n\) warriors, whose order can be arranged arbitrarily) to kill the dragon. If it is impossible to defeat the dragon with the warriors available, output -1.

Note: In a duel between a warrior and the dragon, the warrior will perform rounds equal to \(\lceil H_i/\text{ATK} \rceil\) (since even if the warrior dies at the end of a round, his attack in that round still goes through).

The effective damage a warrior can deal if used as the first fighter is:

\[ \text{damage}_i = \lceil H_i/\text{ATK} \rceil \times A_i \]

If a warrior is the \(k\)-th fighter, his total damage becomes \(k \times \text{damage}_i\). When using several warriors, you can arrange them optimally: assign the warrior with the highest potential damage to the highest multiplier. That is, if you pick \(k\) warriors with potential damages \(d_1, d_2, \dots, d_k\) (in descending order) then the maximum cumulative damage is:

\[ \sum_{i=1}^{k} (k - i + 1) \times d_i\n\]

Your goal is to choose a subset and ordering of warriors so that this total damage is at least \(\text{HP}\) of the dragon, and to minimize the number of warriors used.

inputFormat

The first line contains two integers \(\text{ATK}\) and \(\text{HP}\) of the dragon.

The second line contains an integer \(n\), the number of warriors.

Each of the following \(n\) lines contains two integers \(A_i\) and \(H_i\) representing the attack and health of the \(i\)-th warrior.

outputFormat

Output a single integer: the minimum number of warriors required to defeat the dragon. If it is impossible, output -1.

sample

10 100
3
5 10
10 20
1 100

-1