ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1628. White Streaks

Time limit: 1.0 second
Memory limit: 64 MB
The life of every unlucky person has not only black but also white streaks. The Martian Vas-Vas has a calendar in the form of an m × n table; he marks in this calendar days when he had bad luck. If Vas-Vas had bad luck in the jth day of the ith week, he paints the cell (i, j) black. Initially, all cells are white.
Let rectangles of the form 1 × l or l × 1 be called segments of life. Maximal with respect to inclusion white segments are called white streaks. Can you determine how many white streaks there were in the life of Vas-Vas?


The first line contains integers m, n, and k, which are the size of the calendar and the number of unlucky days in it (1 ≤ m, n ≤ 30000; 0 ≤ k ≤ 60000). In the following k lines, unlucky days are given in the form of pairs (xi, yi), where xi is the number of the week to which the unlucky day belongs and yi is the number of the day within this week (1 ≤ xim; 1 ≤ yin). Every unlucky day is given in the input only once.


Output the number of white streaks in the life of Vas-Vas.


3 5 4
1 1
1 5
2 2
3 3
5 1 2
2 1
3 1
Problem Author: Alexander Ipatov
Problem Source: XIII Open USU Championship