Problem Description

There are $ X $ oranges and $ Y $ mandarins. There are also $ N $ people, and $ N $ is a divisor of $ X + Y $. These $ X + Y $ fruits are to be divided among these $ N $ people such that each person receives exactly $ (X + Y) / N $ fruits.

The $ i $-th person gains a satisfaction of $ A_i $ per orange and $ B_i $ per mandarin. That is, if the $ i $-th person receives $ x $ oranges and $ y $ mandarins, the satisfaction they gain is $ A_i x + B_i y $.

Determine the difference between the highest and lowest satisfaction among the people when the fruits are divided to minimize this difference.

Input Format

The input is given from the standard input in the following format:

$ X $ $ Y $ $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4 5 3
10 5
8 7
4 11

Sample Output #1

3

Sample Input #2

3 5 2
1 1
1000000000 1000000000

Sample Output #2

3999999996

Sample Input #3

30 60 3
1 100
10 1
100 1

Sample Output #3

0

Sample Input #4

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

Sample Output #4

1430

Notes/Hints

Constraints

• $0 \leq X \leq 10^5$
• $0 \leq Y \leq 10^5$
• $X + Y \geq 1$
• $N \geq 2$
• $ N $ is a positive divisor of $ X + Y $.
• $1 \leq A_i, B_i \leq 10^9$ ($1 \leq i \leq N$)
• All input values are integers.

Sample Explanation 1

For example, the minimum difference can be achieved by dividing the fruits as follows:
- The 1st person receives 1 orange and 2 mandarins, gaining a satisfaction of 20.
- The 2nd person receives 1 orange and 2 mandarins, gaining a satisfaction of 22.
- The 3rd person receives 2 oranges and 1 mandarin, gaining a satisfaction of 19.

见题面 Input 部分

见题面 Output 部分