T411780 一道难题(difficult)

有 $X$ 个橙子和 $Y $个苹果。 此外，共有 $N$ 个人， 其中 $N$ 是 $X + Y$ 的约数。 我们将这 $X + Y$ 个水果分成 $N$ 组， 每组恰好分得 $(X + Y) / N$ 个水果。 第 $i$ 个人会从获得一个橙子和一个苹果中得到 $A_i$ 和 $B_i$ 的满足度。也就是说，如果第 $i$ 个人获得 $x$ 个橙子和 $y$ 个苹果，则该人获得的满足度为 $A_i \times x + B_i \times y$。 选取水果分配方式以尽可能减小得到最大满足度和得到最小满足度之间的差，求出差的最小值。

第一行输入 $3$ 个数: $X,Y,N$. 第二行至第 $N+1$ 行输入 $2$ 个数：$ A_i,B_i$。

一个数：最小值。

#### 解释样例 $1$: 最优方案： 第一个人拿 $1$ 个苹果和 $2$ 个橘子，获得 $20$ 的满足度。 第二个人拿 $1$ 个苹果和 $2$ 个橘子，获得 $22$ 的满足度。 第三个人拿 $2$ 个苹果和 $1$ 个橘子，获得 $19$ 的满足度。 $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$ $N\le 10^{6}$ 保证输入的数为正整数。