Одруження
Давним-давно в одній далекій країні правив мудрий цар. У нього було 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), що задовольняють умову задачі.