Evlilik
Çox-çox qədim zamanlarda uzaq bir ölkədə ağıllı bir şah hökmranlıq edirdi. Onun m qızı var idi. Qızlarını ərə vermək vaxtı gəldikdə, şah n qonşu ölkəyə elçilər göndərdi. Bu xəbərə hər ölkədən bir şahzadə gəldi.
Şah qızlarını çox sevən və onların fikirlərini nəzərə alan bir ata olduğu üçün, əvvəlcə şahzadələri sıraya düzməyi tələb etdi, gəncləri 1-dən n-ə qədər nömrələdi və hər qızdan hansı gənclərlə evlənməyə razı olduğunu soruşdu.
Bu ölkənin şahı yaxşı riyazi təhsilə malik idi və bu məlumat əsasında hər qıza sevdiyi gənclərdən birini nişanlamağın mümkün olub-olmadığını yoxlamaq onun üçün çətin olmazdı. Lakin ölkənin hökmdarının maraqlı zəkası belə bir sualla maraqlandı: neçə cütlük (l, r) (1 ≤ l ≤ r ≤ n) var ki, l-dən r-ə qədər nömrələnmiş gənclərdən hər qız üçün bir nişanlı tapmaq olar?
Şaha bu sualın cavabını tapmağa kömək edin!
Giriş məlumatları
Birinci sətirdə üç tam ədəd n, m və k (1 ≤ n ≤ 30 000, 1 ≤ m ≤ 2 000, 1 ≤ k ≤ min(n ∙ m, 100 000)) verilmişdir - müvafiq olaraq gənclərin sayı, qızların sayı və qızların üstünlüklərini təsvir edən sətirlərin sayı.
Növbəti k sətirdə hər biri iki tam ədəd A[i], B[i] (1 ≤ A[i] ≤ n, 1 ≤ B[i] ≤ m) verilmişdir ki, bu da B[i] qızının A[i] gəncini bəyəndiyini göstərir. Bütün qeydlər fərqlidir.
Çıxış məlumatları
Yeganə tam ədəd çıxarın - məsələnin şərtini təmin edən cütlüklərin (l, r) sayını.