In Rainyville, it rains quite a lot. Despite residents getting used to the frequent rain, they still would rather avoid it when walking outside. The side view of a sidewalk (the view as if you were facing the sidewalk from across the street) can be represented by an by grid with rows and columns, where the bottom left corner has coordinates . The rain will come from just above this side view, at row (not visible in this rectangular side view). When walking across this sidewalk, there are certain things that block the rain, such as trees and balconies. The blocks will ensure that each cell within the same vertical column below the block will not be rained on. Consider the following example:
In the diagram, the blue cells represent rain, black represent blocks, and white represent cells safe from the rain. In this example, there is a 6 by 5 grid with blocks at and . Rain falls from the very top, and it will fall until it hits a block, at which point any cells below that block will be safe from the rain. In this case, there are 11 cells safe from the rain. Notice that blocked cells do not count.
Given the blocks in a side view grid of a sidewalk, determine the number of cells that are safe from the rain.
Constraints
It is guaranteed that each blocked cell will be unique.
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints
Input Specification
The first line will contain integers , , and , each separated by a space.
The next lines will contain two spaced integers each, representing the coordinates of the blocked cells (as described in the problem statement).
It is guaranteed that each cell will be unique.
Output Specification
On a single line, output the number of cells that are safe from the rain.
Sample Input 1
6 5 6
0 2
1 4
2 0
2 3
3 1
5 2
Sample Output 1
11
Explanation for Sample Output 1
This is the sample case described in the problem statement.
Sample Input 2
8 8 8
7 6
2 4
5 3
1 1
6 1
3 2
6 4
0 5
Sample Output 2
24
Comments