Generals' Castle Conquest

T1E is obsessed with playing a simplified 1v1 mode of generals. In this simplified version, T1E starts with one castle which produces $x$ units of soldiers at the end of every round, and his opponent has a castle which produces $y$ units of soldiers at the end of every round. Initially (round $0$) both sides have 0 soldiers.

There are n other castles available for T1E to capture. At the beginning of each round, T1E may capture at most one castle. Capturing the i-th castle requires consuming $a_i$ soldiers. Once captured, starting from the next round, that castle will produce an additional 1 soldier at the end of each round for T1E.

T1E wonders what is the earliest round at which his total soldier count will exceed the opponent’s soldier count. If it is impossible for his soldiers to ever exceed the opponent’s, output -1.

The production in each round occurs at the end of the round. The order in a round is as follows:

1. At the beginning of the round, T1E may capture at most one castle provided he has enough soldiers to pay its cost.
2. At the end of the round, T1E’s castle and any captured castles produce soldiers (each castle produces its respective number of soldiers) and the opponent’s castle produces exactly $y$ soldiers.
3. The soldier count is carried over to the next round.

All formulas are in LaTeX format. For example, the production from T1E’s original castle is given by \(x\), the opponent’s production is \(y\), and the cost to capture the i-th castle is \(a_i\).

inputFormat

The first line contains three integers x, y and n representing the soldier production of T1E’s castle, the production of the opponent’s castle, and the number of additional castles respectively.

If n > 0, the second line contains n integers \(a_1, a_2, \dots, a_n\) representing the cost (in soldiers) required to capture each castle. The costs may be given in any order.

outputFormat

Output a single integer representing the earliest round (starting from round 0) at which T1E’s soldier count becomes strictly greater than his opponent’s soldier count. If it is impossible for his soldiers to ever exceed the opponent’s, output -1.

sample

3 2 1
4

1