Bob has a function , which is defined as follows
where , are constants.
Bob has pairs of and (). Bob wants to find some constants and so that he can maximize . Can you help him find out the max possible sum?
Input Specification
The first line of input contains one integer , (), the number of pairs and .
Each of the following lines contains two integers and , ().
Output Specification
Output one integer, the maximum .
Constraints
For all test cases, .
Subtask | Points | Additional constraints |
---|---|---|
and | ||
and | ||
and | ||
No additional constraints. |
Sample Input 1
1
50 0
Sample Output 1
50
Explanation
One possible pair of and is .
Sample Input 2
5
80 20
60 50
40 40
15 10
70 30
Sample Output 2
220
Explanation
One possible pair of and is .
- For , , since , , which is
- For , , since , , which is
- For , , since and , , which is
- For , , since and ,
- For , , since , , which is
Thus, the total sum is . It's the maximum possible sum.
Comments