zuzu

Pe planeta Zuzu toate obiectele sunt caracterizate 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 $x_A, y_A, z_A, x_B, y_B, z_B, 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 și precizări

• $2 \leq n \leq 40$
• $1 \leq t \leq 15$
• Coordonatele colţurilor paralelipipedelor sunt numere reale cu maxim $5$ zecimale şi nu depăşesc în valoare absolută numărul $1000$.

Exemplu

zuzu.in

3 15
0 0 30 10 10 20 6
20.05 0 5 25 5.3 0 1
10 0 10 20 10 0 2  

zuzu.out

2000
10

Explicație

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.