결혼 문제

먼 옛날 아주 먼 나라에 현명한 왕이 살았다. 왕에게는 아름다운 딸이 $M$명 있었고, 마침내 딸들을 시집보낼 때가 되었다. 왕이 이웃한 $N$개 왕국에 전갈을 보내자 각 왕국은 공주와 결혼할 왕자를 한 명씩 보냈다.

왕은 딸의 뜻을 존중했다. 먼저 후보자를 한 줄로 세우고 왼쪽부터 $1$번부터 $N$번까지 번호를 붙인 다음, 각 딸에게 이 후보자 가운데 누구와 결혼할 의향이 있는지 물었다.

왕은 수학에 밝아서 모든 딸의 뜻을 지키면서 딸마다 남편을 한 명씩 정해 줄 수 있는지 판정하는 일은 어렵지 않았다. 그러다 왕은 더 흥미로운 질문을 떠올렸다. $L$번부터 $R$번까지의 후보자만 써서 모든 딸에게 남편을 정해 줄 수 있는 쌍 $(L, R)$ ($1 \le L \le R \le N$)은 몇 개인가?

한 후보자는 많아야 한 명의 딸과 결혼하고, 딸은 자신이 결혼할 의향을 밝힌 후보자와만 결혼한다. 왕의 질문에 답하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$, $M$, $K$가 주어진다. 차례대로 후보자의 수, 딸의 수, 선호 정보가 적힌 줄의 수이다. ($1 \le N \le 30\,000$, $1 \le M \le 2\,000$, $1 \le K \le \min(N \times M, 100\,000)$)

다음 $K$개 줄에 정수 $A_i$, $B_i$가 주어진다. $B_i$번 딸이 $A_i$번 후보자와 결혼할 의향이 있다는 뜻이다. ($1 \le A_i \le N$, $1 \le B_i \le M$) 모든 쌍은 서로 다르다.

첫째 줄에 조건을 만족하는 쌍 $(L, R)$의 개수를 출력한다.

첫 번째 예제에서는 $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 5)$가 조건을 만족한다.