== include(page="template/taskheader" task_id="robotics") ==

Poveste şi cerinţă...

Ne aflăm în secţia de vopsitorie a uzinei _Toyota Motor_ unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorinţa de a
evidenţia calitatea şi viteza de execuţie a roboţilor, inginerii folosesc pentru demonstraţie o tablă de dimensiunea <tex>n \times n</tex>, împărţită în pătrate cu latura egală cu <tex>1</tex>, reprezentată sub forma unui tablou bidimensional cu <tex>n</tex> linii şi <tex>n</tex> coloane.
 
Un robot utilizat pentru vopsire are două braţe telescopice care se deplasează de-a lungul unei axe. Fiecare braţ poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp <tex>t=0</tex> robotul primeşte comanda de a se poziţiona într-un pătrat specificat prin coordonatele <tex>\left ( x, y \right )</tex>.
 
În funcţie de traiectoria de deplasare roboţii folosiţi sunt de două tipuri. La momentul de timp <tex>t</tex> robotul de tip <tex>1</tex> vopseşte pătratele aflate la coordonatele: <tex>\left ( x-t, y+t \right )</tex> şi <tex>\left ( x+t, y-t \right )</tex>, iar robotul de tip <tex>2</tex> vopseşte pătratele aflate la coordonatele: <tex>\left ( x+t, y+t \right )</tex> şi <tex>\left ( x-t, y-t \right )</tex>. Pentru vopsirea unui pătrat se consumă un litru de vopsea. Pe tablă sunt aşezaţi <tex>m</tex> roboţi.
 
h2. Cerinţe
 
Cunoscând pentru cei <tex>m</tex> roboţi coordonatele iniţiale <tex>(x_{i}, y_{i}), i \in \left \{ 1, 2, ..., m \right \}</tex> se cere să se determine:
 
* Cantitatea totală de vopsea care a fost folosită de roboţi după <tex>t</tex> unităţi de timp.
* Numărul minim de unităţi de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecţiei a două traiectorii paralele a doi roboţi de tip <tex>1</tex> cu două traiectorii paralele a doi roboţi de tip <tex>2</tex>, iar colţurile dreptunghiului sunt <tex>4</tex> pătrate care au fost vopsite de doi roboţi de tipuri diferite.

h2. Date de intrare

Fişierul de intrare $robotics.in$ ...

Fişierul de intrare $robotics.in$ conţine pe prima linie trei valori naturale nenule <tex>n</tex>, <tex>m</tex> şi <tex>t</tex>, cu semnificaţiile din enunţ, despărţite prin câte un singur spaţiu.
Pe fiecare dintre următoarele <tex>m</tex> linii se află câte trei valori naturale nenule <tex>x_{i}</tex>, <tex>y_{i}</tex> şi <tex>z_{i}</tex>, despărţite prin câte un spaţiu, unde: <tex>x_{i}, y_{i}</tex> reprezintă coordonatele iniţiale unde se poziţionează robotul <tex>i</tex>, iar <tex>z_{i}</tex> reprezintă tipul robotului.

h2. Date de ieşire

În fişierul de ieşire $robotics.out$ ...

Fişierul de ieşire $robotics.out$ va avea două linii.
Prima linie conţine un număr natural <tex>C</tex> nenul ce reprezintă cantitatea totală de vopsea care este folosită de roboţi după <tex>t</tex> unităţi de timp.
A doua linie conţine un număr natural nenul <tex>T_{min}</tex> ce reprezintă numărul minim de unităţi de timp necesare formării primului dreptunghi de arie nenulă.

h2. Restricţii