SoalWaterfall

Waterfall

Kode soal:	osn1016.PAS/C/CPP
Batas Run-time:	1 detik / test-case
Batas Memori:	32 MB
Sehari sebelum pembagian medali pada Olimpiade Sains Nasional 2010, adalah hari wisata edukasi. Di salah satu lokasi wisata edukasi, Pak Dengklek melihat suatu air terjun buatan.

Air terjun itu mengalir sepanjang tebing yang dapat digambarkan sebagai peta berbentuk matriks dengan ukuran V (secara vertikal) kali H (secara horisontal). Pada tebing tersebut ditempelkan beberapa batu buatan pula (karena air terjunnya pun buatan). Batu buatan tersebut masing-masing berbentuk kotak yang dinyatakan dengan kotak kiri atas dan kanan bawahnya pada peta tebing.

Perhatikan ilustrasi di bawah ini yang menggambarkan sebuah air terjun pada tebing berukuran 5 kali 5 dari kotak (1,1) sampai dengan kotak (5,5). Terdapat tiga batu buatan di posisi (2,3)-(2,4), (4,2)-(5,2), (5,5)-(5,6).


Air terjun tentu tidak lengkap tanpa air itu sendiri, maka air pun perlu diteteskan dari suatu titik pangkal di bagian tebing. Secara spesifik, air akan mulai diteteskan dari sebuah kotak (-1,X). Air tersebut kemudian mungkin menabrak suatu batu. Jika tabrakan itu terjadi, tetesan air akan pecah menjadi dua (dan kedua tetesan tersebut sejak itu dianggap sebagai dua tetes air terpisah; walau suatu saat mereka mungkin bertemu, mereka tetap dianggap dua tetes air yang terpisah). Salah satu satu tetesan air kemudian lanjut menetes dari sisi kiri batu dan satunya lagi lanjut menetes dari sisi kanan batu. Hal tersebut bisa terjadi berulang-ulang sampai tetesan air mencapai dasar air terjun.

Setiap kali air menabrak suatu batu, timbullah suara bergemericik. Pak Dengklek yang merasa bahwa air terjun akan semakin indah jika semakin lebat suara gemericiknya, mengharapkan tabrakan antara air dan batu terjadi sebanyak mungkin. Bantulah Pak Dengklek menentukan di kotak mana air harus mulai diteteskan agar terjadi sebanyak mungkin tabrakan antara air dan batu. Seperti dapat dilihat pada ilustrasi di atas, jika Pak Dengklek meneteskan air dari kotak (-1, 3) akan terjadi 3 tabrakan, sedangkan jika dari kotak (-1, 2) hanya akan terjadi 1 tabrakan. Tabrakan dengan dasar air terjun tidak dihitung.

FORMAT MASUKAN

Baris pertama berisi tiga buah bilangan bulat, V, H, dan N (1 ≤ V, H ≤ 500) yang merupakan ukuran peta air terjun secara vertikal, ukuran peta air terjun secara horisontal, dan banyaknya batu. N baris berikutnya masing-masing berisi empat buah bilangan bulat v1, h1, v2, h2 (semua berada di dalam jangkauan peta) yang menyatakan titik kiri atas dan titik kanan bawah dari batu tersebut. Dijamin tidak ada dua buah batu yang menempel atau bersentuhan satu sama lain sehingga air selalu bisa mengalir.

FORMAT KELUARAN

Sebuah bilangan bulat yang menyatakan banyaknya tabrakan maksimal yang dapat terjadi antara air dan batu jika mulainya tetesan air diatur sedemikian rupa. Bilangan bulat tersebut dijamin tidak lebih besar dari 1015 dan untuk lima puluh persen keluaran bilangan bulat tersebut dijamin tidak lebih besar dari 5000.

CONTOH MASUKAN

6 6 3
2 3 2 4
4 2 5 2
5 5 5 6
CONTOH KELUARAN

3
Penjelasan

Contoh kasus sesuai dengan ilustrasi pada deskripsi soal, tidak ada titik penetesan lain yang dapat menghasilkan tabrakan lebih dari 3 kali.