SPOJ in Armenian

Շատ վաղուց մի հեռավոր երկրում իմաստուն թագավոր էր իշխում։ Նա ուներ, ոչ ավել, ոչ պակաս՝ M աղջիկ։ Ահա եկավ դստրերին ամուսնացնելու ժամանակը, և թագավորը N հարևան երկրներ սուրհանդակներ ուղարկեց։ Այդ լուրը լսելուն պես յուրաքանչյուր երկրից մի արքայազն եկավ։

Լինելով իր դուստրերի կարծիքը հաշվի առնող սիրող հայր, թագավորը առաջին հերթին պահանջեց արաքայազներին շարվել մի շարքով, համարակալեց նրանց 1-ից N թվերով, և հարցրեց իր աղջիկներից յուրաքանչյուրին, թե երիտասարդներից որ մեկի հետ նա կցանկանա ամուսնանալ։

Այդ երկրի թագավորը լավ մաթեմատիկական կրթություն ուներ, և նրա համար դժվար չէր այդ ինֆորմացիայի հիման վրա պարզել, հնարավոր է, արդյոք, իր դուստրերից յուրաքանչյուրին համապատասխանեցնել իր հավանած արքայազներից մեկին։ Բայց երկրի տրիրակալի պրպտուն միտքը տարվեց այսպիսի հարցով. Քանի՞ (L, R) (1<=L<=R<=N) զույգ գոյություն ունի, այնպսին, որ L-ից մինչև R-ը ներառյալ համարներով երիտասարդներից հնարավոր լինի դստրերից յուրաքանչյուրի համար մեկական փեսացու ընտրել։

Օգնեք թագավորին գտնել իր հարցի պատասխանը։

Մուտք

Առաջին տողում տրված են երեք ամբողջ N, M և K թվեր (1<=N<=30000, 1<=M<=2000, 1<=K<=min(N*M, 100000)), համապատասխանաբար, պատանիների քանակը, աղջիկների քանակը և այն տողերի քանակը, որոնցում նկարագրվում են աղջիկների նախասիրությունները։

Հաջորդ K տողերից յուրաքանչյուրում տրված են երկու ամբողջ Ai և Bi ամբողջ թվեր (1<=Ai<=N, 1<=Bi<=M), որոնք նշանակում են, որ Bi աղջկան Ai արքայազնը դուր է գալիս։ Բոլոր գրառումները տարբեր են։

Ելք

Արտածեք մի թիվ՝ խնդրի պայմաններին բավարարող (L, R) զույգերի քանակը։

Օրինակ

Մուտք.
5 3 7
1 1
1 2
1 3
2 3
3 2
4 2
5 1


Ելք.
4

Դիտողություն
Խնդրի պայմաններին բավարարում են (1, 3), (1, 4), (1, 5) և (2, 5) զույգերը։