You are in charge of adding cheese topping to a pizza prepared for a special customer. This pizza is a very long rectangular strip. It is divided into slices, numbered
to
from left to right. To add cheese topping to the pizza, you have a special machine that can add
unit of cheese on each slice in a consecutive group of slices (for example, you can add
unit of cheese on each slice between slice
and
inclusive, adding a total of
units of cheese). Each slice can carry an unlimited amount of cheese.
You plan to run the machine times, each time adding
unit of cheese to each slice in a given range.
The customer is on a diet. When he eats the section of pizza from slice to slice
, inclusive, he would like to know how many units of cheese he is consuming.
NOTE FOR PYTHON USERS: If your program receives TLE (time limit exceeded), you should try submitting using the PyPy interpreter: when you are submitting your code, try using "PyPy 3" or "PyPy 2" as the language, instead of "Python 3" or "Python 2".
Input Specification
The first line will contain the integer , the length of your long pizza.
The second line will consist of two space-separated integers and
, indicating that the customer is planning to eat every slice between slice
and slice
inclusive.
The third line will contain the integer , the number of times you plan to run the topping machine.
The following lines will each describe one planned run of the topping machine using 2 space-separated integers,
and
, indicating that the machine will add
unit of cheese onto each slice between slices
and
, inclusive.
Output Specification
Please output the total number of units of cheese on all of the slices the customer is planning to eat.
Constraints and Partial Marks
For of the
available marks,
and
.
For the remaining marks,
and
.
Sample Input
10
3 5
3
2 6
4 5
3 3
Sample Output
6
Explanation of Sample Output
After running the machine three times, the amount of cheese on each slice of pizza is as follows:
Slice #: 1 2 3 4 5 6 7 8 9 10
Cheese: 0 1 2 2 2 1 0 0 0 0
Therefore, slices to
have a total of
units of cheese.
Comments