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 ≤ xi ≤ m; 1 ≤
yi ≤ n). Every unlucky day is given in the
input only once.
Output the number of white streaks in the life of
3 5 4
5 1 2
Problem Author: Alexander Ipatov
Problem Source: XIII Open USU Championship