Segmente

Considerăm $N$ segmente în planul XOY. Segmentele sunt fie orizontale (paralele cu axa OX), fie verticale (paralele cu axa OY) şi au capetele în puncte de coordonate întregi. De asemenea, nu există două segmente orizontale situate pe aceeaşi dreaptă şi nici două segmente verticale situate pe aceeaşi dreaptă. Tuturor segmentelor li se poate aplica simultan o operaţie de prelungire la ambele capete cu o valoare întreagă $D$. Pentru orice segment, dacă lungimea este $L$, atunci după prelungire dimensiunea sa este $L + 2 \cdot D$.

Cerinţă

Să se determine valoarea minimă $D$ cu care trebuie prelungite segmentele astfel încât după prelungire segmentele să închidă cel puţin un dreptunghi.

Date de intrare

Pe prima linie a fişierului segmente.in se află un număr natural $N$ reprezentând numărul de segmente. Pe fiecare din următoarele $N$ linii se găsesc câte patru numere întregi $x_1 y_1 x_2 y_2$. Primele două reprezintă un capăt al segmentului, iar ultimele două celălalt capăt.

Date de ieșire

Pe prima linie a fişierului segmente.out, se va scrie un număr natural $D$ reprezentând dimensiunea minimă necesară prelungirii tuturor segmentelor pentru a se forma cel puţin un dreptunghi.

Restricții și precizări

• $4 ≤ N ≤ 1 \ 000$
• capetele segmentelor sunt numere întregi din intervalul $[-500 \ 000 \ 000, 500 \ 000 \ 000]$
• Orice segment are lungimea iniţială de cel puţin $1$
• Pentru datele de intrare, nu există iniţial niciun dreptunghi deja format; de asemenea, vor exista cel puţin $2$ segmente verticale şi cel puţin două orizontale
• Se garantează că există o soluţie cu $1 ≤ D ≤ 1 \ 000 \ 000 \ 000$
• Pentru $50\%$ din teste, $N ≤ 200$

Exemplu

segmente.in

5
1 2 1 3
3 2 4 2
2 3 2 5
5 2 5 7
5 6 7 6

segmente.out

3

Explicație

Figura 1 din enunțul original al problemei Segmente.Mărește schema ↗

Segmentele iniţiale sunt cele îngroşate, cu linie punctată sunt extinderile cu $3$ unităţi la ambele capete ale tuturor segmentelor, iar haşurat este marcat dreptunghiul care s-a format după prelungirea cu $D = 3$.