Женитьба
Давным давно в одной далёкой стране правил мудрый царь. И было у него ни много, ни мало - m дочерей. Вот настало время выдавать дочерей замуж, и послал царь гонцов в n соседних государств. На эту весть съехалось по одному принцу от каждого государства.
Так как царь был любящим отцом, учитывающим мнение своих дочерей, первым делом он потребовал принцев выстроиться в ряд, занумеровал юношей числами от 1 до n, и спросил у каждой дочери, с какими из стоящих молодых людей она согласна сыграть свадьбу.
У царя этой страны было хорошее математическое образование, и ему не составило бы труда по этой информации проверить, можно ли назначить каждой дочери своего жениха из числа симпатичных ей молодых людей. Но пытливый ум правителя страны заинтересовал такой вопрос: сколько существует пар (l, r) (1 ≤ l ≤ r ≤ n), таких, что из юношей с номерами от l до r включительно можно найти по жениху для каждой из дочерей?
Помогите царю найти ответ на его вопрос!
Входные данные
В первой строке заданы три целых числа n, m и k (1 ≤ n ≤ 30 000, 1 ≤ m ≤ 2 000, 1 ≤ k ≤ min(n ∙ m, 100 000)) - соответственно количество юношей, количество девушек и количество строк, описывающих предпочтения девушек.
В каждой из следующих k строк записаны два целых чисел A[i], B[i] (1 ≤ A[i] ≤ n, 1 ≤ B[i] ≤ m), которые означают, что девушке B[i] нравится юноша A[i]. Все записи различны.
Выходные данные
Выведите единственное целое число - количество пар (l, r), удовлетворяющих условию задачи.