Muzeul municipal se mută în altă locaţie şi toate cele n obiecte expuse trebuie transportate.
Avem la dispoziţie m cutii în care le putem împacheta. Fiindcă obiectele sunt foarte valoroase trebuie să găsim o
modalitate de împachetare cât mai sigură. Pentru simplitate vom considera obiectele şi cutiile de forma paralelipipedică. Dacă un obiect de dimensiuni (x,y,z) este împachetat într-o cutie de dimensiuni
(a,b,c), definim gradul de siguranţă ca: max(a-x,b-y,c-z). Evident, obiectele se pot roti, pentru a obţine un grad
de siguranţă mai mic. Un obiect nu se poate împacheta intr-o cutie care are o mărime corespunzătoare mai mică,
adică, pentru a putea împacheta obiectul trebuie ca a>=x, b>=y şi c>=z.
Cerinţă
Să se găsească modalitatea de împachetare prin care se minimizează cel mai mare grad de siguranţă.
Date de intrare
Pe prima linie a fişierului de intrare pack.in se află numărul n
al obiectelor. Pe următoarele n linii se găsesc câte trei numere întregi reprezentând mărimea
obiectelor. Pe a (n+2)-a linie se află numărul m al cutiilor. Pe
următoarele m linii se găsesc câte trei numere întregi reprezentând dimensiunile cutiilor.
Date de ieşire
Pe prima linie a fişierului de ieşire pack.out să se afişeze gradul
de siguranţă minim cu care se poate realiza împachetarea. Pe următoarele n linii se vor scrie
câte două numere i şi j cu semnificaţia că obiectul i s-a împachetat în cutia j. Dacă nu se pot împacheta toate
obiectele, în fişierul de ieşire se va afişa -1.
Restricţii
1 <= n <= m <= 500
1 <= x, y, z, a, b, c <= 1000
Dacă există mai multe soluţii puteţi afişa oricare dintre acestea.