Marriage questions

Long ago, in a country far away, a wise king had $M$ beautiful daughters. The time for them to marry finally came. The king sent word to $N$ neighboring kingdoms, and every kingdom sent one prince to marry a princess.

The king respected his daughters' wishes. He lined the candidates up, numbered them $1$ to $N$ from the left, and asked each daughter which of these candidates she was willing to marry.

The king knew mathematics well, so deciding whether every daughter could be given a husband while every wish is respected was easy for him. Then he thought of a more interesting question: how many pairs $(L, R)$ ($1 \le L \le R \le N$) are there such that every daughter can be given a husband using only the candidates numbered $L$ to $R$?

A candidate marries at most one daughter, and a daughter marries only a candidate she said she was willing to marry. Write a program that answers the king's question.

The first line contains the integers $N$, $M$, and $K$: the number of candidates, the number of daughters, and the number of lines describing the daughters' preferences. ($1 \le N \le 30\,000$, $1 \le M \le 2\,000$, $1 \le K \le \min(N \times M, 100\,000)$)

Each of the next $K$ lines contains the integers $A_i$ and $B_i$, meaning that daughter $B_i$ is willing to marry candidate $A_i$. ($1 \le A_i \le N$, $1 \le B_i \le M$) All pairs are different.

Print the number of pairs $(L, R)$ that satisfy the condition.

In the first example the pairs $(1, 3)$, $(1, 4)$, $(1, 5)$, and $(2, 5)$ satisfy the condition.