問題文

オレンジが 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 となります。

最も大きい満足度を得る人の満足度と最も小さい満足度を得る人の満足度の差をできるだけ小さくするように果物の分け方を選んだときの、この差を求めてください。

制約

• 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)
• 入力値はすべて整数である。

入力例 1

4 5 3
10 5
8 7
4 11

出力例 1

3

たとえば以下のように果物を分けることで最小値を達成できます。

• 1 人目はオレンジを 1 個、みかんを 2 個受け取る。20 の満足度を得る。
• 2 人目はオレンジを 1 個、みかんを 2 個受け取る。22 の満足度を得る。
• 3 人目はオレンジを 2 個、みかんを 1 個受け取る。19 の満足度を得る。

入力例 2

3 5 2
1 1
1000000000 1000000000

出力例 2

3999999996

入力例 3

30 60 3
1 100
10 1
100 1

出力例 3

0

入力例 4

1000 1000 5
41 60
78 10
19 100
100 40
30 40

出力例 4

1430