Одруження#7474
Давним-давно в одній далекій країні правив мудрий цар. У нього було дочок. Коли настав час видавати їх заміж, цар відправив гінців у сусідніх держав. На цю звістку з кожної держави прибув один принц.
Цар, будучи люблячим батьком, враховував думку своїх дочок. Він наказав принцам вишикуватися в ряд і пронумерував їх від до . Потім він запитав кожну дочку, з якими з цих принців вона згодна одружитися.
Цар мав добру математичну освіту, тому міг легко визначити, чи можна призначити кожній дочці нареченого з числа тих, хто їй подобається. Однак його зацікавило інше питання: скільки існує пар (l, r) (1 \leq l \leq r \leq n), таких, що серед принців з номерами від до включно можна знайти нареченого для кожної з дочок?
Допоможіть царю знайти відповідь на його питання!
У першому рядку задано три цілі числа , і (1 \leq n \leq 30\,000, 1 \leq m \leq 2\,000, 1 \leq k \leq \min(n \cdot m, 100\,000)) - відповідно кількість принців, кількість дочок і кількість рядків, що описують вподобання дочок.
У кожному з наступних рядків записано два цілі числа A_i, B_i (1 \leq A_i \leq n, 1 \leq B_i \leq m), які означають, що дочці B_i подобається принц A_i. Усі записи різні.
Виведіть єдине ціле число - кількість пар (l, r), що задовольняють умову задачі.
Приклад 1