Masala #4ALQHR2IYN

O‘z kvartirasini sotib olganidan keyin Boriy har bir xonaga oboylar yopishtirishga qaror qildi. Boriyning kvartirasida n ta xona bor, har biri to‘rtburchak parallelepiped shakliga ega. Har bir xona uchun devorlarning uzunligi, eni va balandligi metrda ma'lum (turli xonalar har xil o‘lchamlarga ega bo‘lishi, shu jumladan balandligi ham farq qilishi mumkin).

Boriy m turdagi oboylarni tanladi, ular bilan u xonalarining devorlarini yopishtirishni rejalashtirmoqda (lekin hamma turlarini ishlatish shart emas). Har bir oboy turi o‘ralgan rulonlarda sotiladi, rulonlarning uzunligi va eni aniq belgilangan (albatta, rulon to‘liq yozilgan holatda o‘lchanadi). Bundan tashqari, har bir turdagi rulonning narxi ham ma'lum.

Har bir oboy turida chiziqlar bor, ular rulonning uzunligi bo‘ylab vertikal joylashgan. Yopishtirilganda chiziqlar faqat qattiq vertikal joylashishi kerak (shuning uchun rulonni aylantirib bo‘lmaydi, hattoki uning uzunligi kenglikdan qisqa bo‘lsa ham). Rulonlarni erkin kesish mumkin, lekin yopishtirilgan qismlarning tutashuvlari ham vertikal bo‘lishi shart. Bundan tashqari, har bir xonada faqat bir turdagi oboy ishlatilishi kerak va bitta rulonning qismlarini turli xonalarga yopishtirish mumkin emas, ya’ni har bir xona uchun rulonlar alohida xarid qilinadi. Ba'zi rulonlardan to‘liq foydalanilmasligi ham mumkin.

Kvartira sotib olgandan keyin Boriyning moliyaviy ahvoli yaxshi emas, shuning uchun u oboylarga minimal mablag‘ sarflashni xohlaydi. Unga yordam bering.

Birinchi qatorda n (1 ≤ n ≤ 500) — Boriyning kvartirasidagi xonalar soni beriladi.

Keyingi n qatorning har birida 3 ta bo‘shliq bilan ajratilgan natural sonlar keltiriladi — navbatdagi xonaning devorlarining uzunligi, eni va balandligi (metrlarda).

Keyingi qatorda m (1 ≤ m ≤ 500) — mavjud oboy turlari soni keltiriladi.

Keyingi m qatorning har birida 3 ta bo‘shliq bilan ajratilgan natural sonlar keltiriladi — navbatdagi oboy turining uzunligi, eni (metrlarda) va bitta rulonning narxi.

Kiritish ma'lumotlaridagi barcha sonlar 500 dan oshmaydi. Har bir xonani mavjud oboy turlari yordamida yopishtirish mumkinligi kafolatlanadi.

Bitta sonni chiqaring — rulonlarning minimal umumiy qiymati. Agar buni iloji bo'lmasa -1.