Pe planeta Zuzu toate obiectele sunt caracteri¬zate prin faptul că au formă paralelipipedică. Mai mult, chiar şi norii au forma unor paralelipipede dreptunghice. La un moment dat cerul se întunecă şi deasupra unei zone a planetei Zuzu apar n nori, evident toţi în formă de paralelipiped dreptunghic. Considerând un sistem de axe tridimensional cu Ox, Oy şi Oz perpendiculare, două câte două, se observă faptul că toţi norii au toate laturile paralele cu axele. Pentru fiecare nor se cunosc coordonatele (date în metri) a două colţuri: cel din stânga-sus-spate (punctul A), respectiv cel din dreapta-jos-faţă (punctul B), ca în figura alăturată:
Norii pot să treacă unii prin alţii şi se pot deplasa doar în şase sensuri: în sensul axei Ox (sens notat cu 1), în sens opus axei Ox (sens notat cu 2), în sensul axei Oy (sens notat cu 3), în sens opus axei Oy (sens notat cu 4), în sensul axei Oz (sens notat cu 5), în sens opus axei Oz (sens notat cu 6). La fiecare unitate de timp fiecare nor se deplasează cu câte 1 metru pe direcţia sa de deplasare. Prin întrepă¬trunderea şi lipirea norilor se pot forma formaţiuni noroase (o formaţiune noroasă poate fi formată şi dintr-un singur nor). Un nor face parte dintr-o formaţiune noroasă, dacă are în comun cel puţin un paralelipiped dreptunghic sau un dreptunghi cu alt nor din ea. Norii dispar, ca din senin, după t unităţi de timp.
Cerinţă
Să se determine volumul maxim al unei formaţiuni noroase şi după cât timp se realizează formaţiunea respectivă. Dacă există mai multe formaţiuni cu acelaşi volum maxim, se cere timpul minim la care se obţine o astfel de formaţiune.
Date de intrare
Fişierul de intrare zuzu.in conţine pe prima linie numerele naturale n şi t separate printr-un spaţiu, iar pe următoarele n linii şapte numere reale xA, yA, zA, xB, yB, zB, s separate între ele prin câte un spaţiu. Primele trei numere sunt coordonatele colţului A, următoarele trei numere sunt coordonatele punctului B, iar s poate fi una dintre cifrele 1, 2, 3, 4, 5, 6 şi este sensul de deplasare pentru un norul respectiv.
Date de ieşire
În fişierul zuzu.out se va scrie pe prima linie volumul (partea sa întreagă), iar pe a doua linie numărul de unităţi de timp din cerinţă.
Restricţii
2 <= n <= 40
1 <= t <= 15
Coordonatele colţurilor paralelipipedelor sunt numere reale cu maxim 5 zecimale şi nu depăşesc în valoare absolută numărul 1000.
După 0 unităţi de timp formaţiunea noroasă cea mai mare are volumul 1000 şi este alcătuită din norul 1. … După 10 unităţi de timp formaţiunea noroasă cea mai mare are volumul 2000 şi este alcătuită din norii 1 şi 3 (au o faţă comună). … Pentru 15 unităţi de timp nu se mai determină formaţiuni noroase, deoarece acestea dispar.
