AT_code_festival_2018_quala_e オレンジとみかん

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_e オレンジが $ X $ 個、みかんが $ Y $ 個あります。 また、人が $ N $ 人おり、$ N $ は $ X\ +\ Y $ の約数となっています。 これら $ X\ +\ Y $ 個の果物を、各人がちょうど $ (X\ +\ Y)\ /\ N $ 個の果物を受け取るように、これら $ N $ 人で分けることにしました。 $ i $ 人目の人はオレンジ $ 1 $ 個あたり $ A_i $、みかん $ 1 $ 個あたり $ B_i $ の満足度を得ます。 すなわち、$ i $ 人目の人がオレンジを $ x $ 個、みかんを $ y $ 個受け取った場合、この人が得る満足度は $ A_i\ x\ +\ B_i\ y $ となります。 最も大きい満足度を得る人の満足度と最も小さい満足度を得る人の満足度の差をできるだけ小さくするように果物の分け方を選んだときの、この差を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ X $ $ Y $ $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $

答えを出力せよ。

### 制約 - $ 0\ \leq\ X\ \leq\ 10^5 $ - $ 0\ \leq\ Y\ \leq\ 10^5 $ - $ X\ +\ Y\ \geq\ 1 $ - $ N\ \geq\ 2 $ - $ N $ は $ X\ +\ Y $ の正の約数である。 - $ 1\ \leq\ A_i,\ B_i\ \leq\ 10^9 $ ($ 1\ \leq\ i\ \leq\ N $) - 入力値はすべて整数である。 ### Sample Explanation 1 たとえば以下のように果物を分けることで最小値を達成できます。 - $ 1 $ 人目はオレンジを $ 1 $ 個、みかんを $ 2 $ 個受け取る。$ 20 $ の満足度を得る。 - $ 2 $ 人目はオレンジを $ 1 $ 個、みかんを $ 2 $ 個受け取る。$ 22 $ の満足度を得る。 - $ 3 $ 人目はオレンジを $ 2 $ 個、みかんを $ 1 $ 個受け取る。$ 19 $ の満足度を得る。