Laiko ribojimas: 1s

Atminties ribojimas: 32MB

Duomenų failas: dumai.in

Rezultatų failas: dumai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Dūmų pranešimas

Trys indėnų gentys nori įsikurti naujame slėnyje, tačiau kai kuriose slėnio vietose pastatyti tipį (palapinę) yra lengviau nei kitose. Tam, kad būtų paprasčiau išsirinkti vietą, senoliai nubraižė slėnio žemėlapį, kuriame pažymėjo galimas gyvenviečių koordinates bei gyvenvietės įrengimo lengvumą (didesnis skaičius reiškia mažesnę statymo kainą).

Dabar jiems teliko išsirinkti tris vietas, kuriose įrengti gyvenvietes būtų lengviausia. Tačiau jie taip pat norėtų, kad ir kokioje gyvenvietėje būtų užkurtas laužas (siųsti dūmų signalams), kitos gyvenvietės taip pat turėtų matyti dūmus, t.y. nei viena gyvenvietė neturėtų užstoti kitos.

Įvestis

Pirmoje eilutėje bus pateiktas skaičius 3\\leqn\\leq10^5 - galimų gyvenviečių kiekis. Sekančiose n eilutėse bus pateikta informacija apie gyvenvietes: -10^5\\leqx,y\\leq10^5 - gyvenvietės koordinatės ir 0\\leqs\\leq10^5 - pastatymo lengvumas.

Rezultatai

Pirmoje eilutėje parašykite maksimalų gyvenviečių įrengimo lengvumą. Sekančioje eilutėje išveskite vietų, kuriose reikia statyti tris gyvenvietes, indeksus.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
0 0 1
0 1 2
0 2 3
0 4 4
1 0 5
 
12
5 4 3