问题描述

现在有 $X$ 个橙子和 $Y$ 个柑橘。此外，有 $N$ 个人，其中 $N$ 是 $X + Y$ 的约数。我们打算将这 $X + Y$ 个水果分给这 $N$ 个人，使得每个人恰好获得 $(X + Y) / N$ 个水果。

第 $i$ 个人对于每个橙子都有满足度 $A_i$，对于每个柑橘都有满足度 $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 个橙子和 2 个柑橘。他的满足度为 20。
• 第二个人获得 1 个橙子和 2 个柑橘。他的满足度为 22。
• 第三个人获得 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