Fişierul intrare/ieşire:	h.in, h.out	Sursă	Happy Coding 2007
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.75 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

H

Gigel are N segmente verticale, numerotate de la 1 la N. Un segment K este caracterizat prin valorile X_K, Yjos_K si Ysus_K. Coordonatele capatului de jos al segmentului K sunt (X_K,Yjos_K), iar coordonatele capatului de sus sunt (X_K,Ysus_K). Gigel vrea sa aleaga doua dintre aceste segmente si sa le "taie" in asa fel incat ambele sa aiba aceeasi valoare pentru Yjos, respectiv pentru Ysus. Presupunand ca segmentele alese sunt A si B, noua valoare a lui Yjos pentru fiecare din cele doua segmente va fi max{Yjos_A,Yjos_B}, iar noua valoare a lui Ysus pentru fiecare din cele doua segmente va fi min{Ysus_A,Ysus_B}. Sa notam prin YJ valoarea max{Yjos_A,Yjos_B} si prin YS valoarea min{Ysus_A,Ysus_B}. Daca nu este adevarata relatia YJ ≤ YS, atunci perechea de segmente (A,B) nu este valida (iar Gigel nu ar alege niciodata o pereche invalida). Pentru o pereche valida de segmente (A,B), dupa operatia de "taiere" a segmentelor, el va uni segmentele printr-un segment orizontal, pentru a forma o figura care seamana foarte mult cu litera "H". Segmentul orizontal va fi trasat intre coordonatele (X_A,Y) si (X_B,Y), cu YJ ≤ Y ≤ YS (nu este importanta valoarea exacta a coordonatei Y a segmentului trasat). Dupa obtinerea literei "H", Gigel calculeaza "lungimea" acesteia. Lungimea literei "H" este definita ca fiind suma celor 3 laturi ale literei: 2*(YS-YJ)+|X_B-X_A|.

Ajutati-l pe Gigel sa aleaga o pereche valida de segmente pentru care lungimea literei H obtinuite sa fie maxima.

Date de intrare

Prima linie a fisierului de intrare h.in contine numarul intreg contine numarul intreg N, reprezentand numarul de segmente verticale. Fiecare din urmatoarele N linii contine 3 numere intregi, separate prin cate un spatiu: X, Yjos, Ysus (avand semnificatia mentionata anterior). A K-a linie dintre aceste N linii contine valorile ce caracterizeaza al K-lea segment.

Date de iesire

Fisierul de iesire h.out va contine un numar intreg reprezentand lungimea maxima a unei litere H pe care o poate desena Gigel conform procedeului mentionat.

Restrictii

• 1 ≤ N ≤ 65535
• Pentru fiecare segment:
  • 0 ≤ X, Yjos, Ysus ≤ 100 000 000
  • Yjos ≤ Ysus
• Va exista cel putin o pereche valida de segmente.

Exemplu

Cum se trimit solutii?