Kang the Penguin thinks that Farmer John's robot plow (Linky!) is a failure, since it can only plow a field that is 240 by 240 at best. Thus, he wishes to suan it with his speciality Penguin Plow (tm), which can plow a field that is at most 240 by 1,000,000,000 in dimensions. Help him with his task!
Input and Output
Exactly the same as in the Robot Plow question (see above), except that the Y variable(s) may take values up to 1,000,000,000 and there may be up to 20,000 plow instructions.
Grading
10% of all test cases will have limits similar to the robot plow (240 by 240).
Sample Input 1
6 4 2
1 1 2 4
1 3 5 4
Sample Output 1
14
Explanation for Sample Output 1
Check the explanation in rplow.