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

In taramul Alexandria a fost dezvoltata o noua tehnologie de transport in comun: nave interdimensionale.

Alex tocmai a redescoperit un joc din copilărie de care este atât de încântat încât s-a gândit să-l propună la concursul Autumn WarmUp 2020. Cum probabil v-aţi aşteptat deja, el oferă 100 de puncte ca recompensă celor care rezolvă corect jocul.

In Alexandria exista <tex> N </tex> nave interdimensionale si fiecare nava este caracterizata de coordonatele sale in <tex> K </tex> dimensiuni distincte. Lui Alex nu-i place modul in care sunt amplasate aceste nave in spatiu si a decis sa le mute astfel incat pe fiecare dimensiune sa exista cel putin <tex> P </tex> nave distincte cu coordonate distincte. El poate consuma un punct de energie pentru a

Fie N nave planare aflate la diferite coordonate întregi (x, y). În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă i aflată la poziţia (xi, yi) şi se mută în una dintre cele 4 poziţii vecine: (xi+1, yi), (xi-1, yi), (xi, yi+1), (xi, yi-1).
 
Alex vrea să afle numărul minim de secunde după care vor fi cel puţin K linii cu măcar o navă şi cel puţin K coloane cu măcar o navă.

h2. Date de intrare