Taisnstūri un nogrieznis

Uzdevums

Plaknē izvietoti N taisnstūri, kuru malas ir paralēlas koordinātu asīm. Taisnstūri var pārklāties, sakrist vai atrasties viens otra iekšpusē. Visu taisnstūru virsotņu koordinātas ir veseli nenegatīvi skaitļi un x koordināta nepārsniedz x_max un y koordināta nepārsniedz y_max. Ir novilkts nogrieznis AB, kura viens galapunkts atrodas punktā A(0, 0), bet otrs galapunkts B apmierina sekojošus nosacījumus:

• tā koordinātas ir veseli skaitļi;
• tas pieder vai nu nogrieznim [(0, y_max), (x_max, y _max)] , vai arī nogrieznim [(x_max, 0), (x_max, y_max)];

Uzrakstiet programmu, kas nosaka, kādu lielāko taisnstūru skaitu var krustot nogrieznis AB!

Ievaddati

Teksta faila taisnstn.dat pirmajā rindā dotas trīs naturālu skaitļu x_max, y_max (0< x_max, y_max ≤10⁹ ) un N (1≤N≤10000) vērtības. Katrā no nākošajām N rindām dots viena taisnstūra apraksts kā četru veselu skaitļu vērtības: apakšējā kreisā stūra koordinātas x_apkr un y_apkr un augšējā labā stūra koordinātas x_aula un y_aula . Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.

Izvaddati

Teksta faila taisnstn.rez vienīgajā rindā jāizvada viens vesels skaitlis - lielākais taisnstūru skaits, ko var šķērsot nogrieznis AB.

Piemērs

taisnstn.dat	taisnstn.rez
22 14 8 1 8 7 11 18 10 20 12 17 1 19 7 12 2 16 3 16 7 19 9 8 4 12 11 7 4 9 6 10 5 11 6	5

Punkts B var būt (22,11) vai (22,12).

Atsauces