Давным давно в одной далёкой стране правил мудрый царь. И было у него ни много, ни мало - 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 строк записаны два целых чисел Ai, Bi (1 ≤ Ai ≤ n, 1 ≤ Bi ≤ m), которые означают, что девушке Bi нравится юноша Ai. Все записи различны.

Выходные данные

Выведите единственное целое число - количество пар (l, r), удовлетворяющих условию задачи.