Marriage questions#7474
Once upon a time in a country far, far away, the wise king had beautiful daughters. At last, the time for them to get married has come. King sent a message in neighboring kingdoms, so each of them sent a prince to marry one of the princesses.
As a loving father the king considered his daughters' opinions. First of all he arranged young men in a line, enumerated them with numbers from to , and asked each of his daughters, with whom from those candidates she would agree to get married.
King had an excellent mathematical background, so it was easy for him to check whether it is possible to find a husband for each of his daughters in such a way, that requests of each daughter were satisfied. But suddenly the king thought about more interesting question: how many pairs (l, r) (1 \leq l \leq r \leq n) are there, such that it is possible to assign a husband for each daughter, using only candidates with numbers from to inclusive?
Help king to find an answer to his question!
First line contains three integers , and (1 \leq n \leq 30\,000, 1 \leq m \leq 2\,000, 1 \leq k \leq \min(n \cdot m, 100\,000)) - number of candidates, number of girls and number of lines, describing girls' preferences respectively.
In next lines there are two integers A_i, B_i (1 \leq A_i \leq n, 1 \leq B_i \leq m), it means that girl B_i likes candidate A_i. All pairs are different.
Output the number of ways king can choose a pair (l, r) to satisfy the problem statement.
Example 1