Masala #P1BSREENCR

Va nihoyat uzoq ish kunidan so'ng sovg'a qadoqlash zalidagi ishlar yakunlandi. Barcha sovg'alar qadoqlanib, qoplarga solinib, Qorboboning chanasiga joylanib tayyor holatga keltirildi. Sovg'a qadoqlash zali esa yaroqsiz sovg'a qutilari va lentalar sochilganicha tartibsiz holatda qoldi. Uni tozalash sizning vazifangiz, xavotir olmang uni qo'lda tozalab chiqmaysiz 😄.

Sovg'a qadoqlash zali N*M o'lchamda, zalga K ta tozalovchi robotni joylashtirib chiqgansiz. Har bir robotning turgan joyi aniq va ular zalning o'zi turgan koordinatasini tozalaydi. Hamma robotlar uchun sizda bitta boshqaruv pulti bor, robotlar pultdan kelgan buyruqni sinxron ravishda bir vaqtda bajaradi. Pult 4 ta tugmadan iborat, tugmalar yordamida robotlarna orqaga, oldinga, o'ngga va chapga harakatlantirish mumkin. Agar robot zal devoriga urilib ketsa ishdan chiqishi mumkin, robotlar juda qimmat bo'lgani uchun birorta ham robot ishdan chiqmasligi kerak.

Robotlarni birinchi taxlab qo'ygan holatingizda eng ko'pi bilan zalning qancha qismini tozalash mumkin? Robotlarni faqat pult bilan boshqarish mumkin, ularni alohida qayta joylashtirish mumkin emas.

Birinchi qatorda N, M va K sonlari, N va M zalning o'lchami, K esa robotlar soni. \(K \leq N*M \leq 10^6\)

Keyingi K ta qatorda 2 tadan son, i-qatordagi sonlar i-robotning joylashgan koordinatasini bildiradi.

Zalning tozalash mumkin bo'lgan maksimal yuzasi.