Dê Non

Xem PDF

Điểm: 200 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami sẽ kể các bạn nghe về hành trình vượt bao gian khó để đoạt được vũ khí tối thượng. Có tất cả 6 vũ khí, tương ứng với mỗi ải mà ami sẽ phải vượt qua.

Ải đầu tiên được trấn giữ bởi xạ thủ dê non dungde99. Ami sẽ phải chiến thằng trong ván cờ vua với dê non để đoạt được vũ khí là sừng dê siêu nhọn.

Dê non dungde99 đã bố trí \(k\) con xe trên 1 bàn cờ \(m \times n\) (\(m\) hàng, \(n\) cột). ami sẽ phải đặt một con vua lên bàn cờ sao cho vua không bị chiếu. ami, với bản năng sát thủ của mình đã ngay lập tức chiến thắng thử thách này. Bây giờ, ami muốn hỏi các bạn, có bao nhiêu cách đặt con vua như vậy ?

Input

  • Dòng đầu tiên chứa 3 số nguyên dương \(m, n, k \ (k \leq \min(mn, 10^5))\) lần lượt là kích cỡ bàn cờ và số con xe của dungde99

  • \(k\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(x, y \ (1 \leq x \leq m; 1 \leq y \leq n)\), tọa độ của một con xe.

  • \(k\) con xe nằm ở \(k\) vị trí khác nhau.

Output

  • In ra một số nguyên dương là số vị trí ami có thể đặt con vua.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(m, n \leq 20\)

  • Subtask \(2\) (\(10\%\) số điểm): \(m, n \leq 100\)

  • Subtask \(3\) (\(20\%\) số điểm): \(m, n \leq 1000\)

  • Subtask \(4\) (\(30\%\) số điểm): \(m, n \leq 100000\)

  • Subtask \(5\) (\(30\%\) số điểm): \(m, n \leq 10^9\)

Example

Test 1

Input
2 3 2
1 1
1 3
Output
1
Note

Chỉ có 1 vị trí đặt vua là \((2, 2)\).


Bình luận

Không có bình luận nào.