E - オレンジとみかん
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
オレンジが 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)
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y N A_1 B_1 A_2 B_2 : A_N B_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