← 返回题目列表

AtCoder · code_festival_2018_quala_e

E. 橙子和橘子

中文机器翻译题面 查看原题

配点 : 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