Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Bokštas

Ant stalo iš eilės sustatyta n (1\\leqn\\leq1000) dėžių. Jūs žinote kiekvienos dėžės matmenis: i-osios dėžės plotis yra w_i, ilgis - l_i, o aukštis - h_i (1\\leqw_i,h_i,l_i\\leq10^6). Iš šių dėžių norite pastatyti kuo aukštesnį bokštą. Tačiau vieną dėžę galima dėti ant kitos tada ir tik tada, jei aukščiau esanačios dėžės tiek plotis, tiek ilgis yra griežtai mažesni už žemesniosios dėžės tiek plotį, tiek ilgį. Formaliai, ant i-osios dėžės galėsime uždėti j-ąją, jei w_j<w_i ir l_j<l_i. Dėžių sukioti ar vartyti negalite. Raskite aukščiausio įmanomo bokšto aukštį.

Pradiniai duomenys

Pirmoje eilutėje pateiktas skaičius n. Toliau seka n eilučių. i-ojoje iš jų pateikti trys skaičiai: w_i, l_i ir h_i.

Rezultatai

Išveskite vieną skaičių - aukščiausio įmanomo bokšto aukštį.

Pavyzdys

Duomenys Rezultatai 
4
3 4 1
2 4 3
1 1 4
4 3 4
 
8