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

Lui Lucy ii plac mult florile roz si poligoanele convexe. Ea cunoaste locatia a $N$ gradini (gradinile sunt reprezentate ca puncte in plan) ce contin multe flori roz si isi doreste ca mergand calare pe unicornul ei, sa viziteze unele din gradini astfel incat sa vada in total un numar maxim de flori. Intre oricare doua gradini exista un singur drum direct format din segmentul ce le uneste. O alta dorinta a ei este ca traseul parcurs sa aiba forma unui poligon convex. Ea va porni tot timpul de la casa ei situata in originea planului (coordonata $0, 0$) si se va intoarce tot aici la finalul traseului. Determinati numarul maxim de flori ce il poate vedea.

Poveste si cerinta...

h2. Date de intrare

Pe prima linie a fisierului de intrare $polig.in$ se afla $N$ avand semnificatia din enunt, iar pe urmatoarele $N$ linii trei numere intregi $x$, $y$ si $c$, cele de pe linia $i+1$ reprezentand coordonatele si numarul de flori din gradina $i$.

Pe prima linie a fisierului Polig.in se gaseste n numarul de puncte, iar pe urmatoarele n linii trei numere intregi x,y,c reprezentand coordonatele si costul punctului respectiv.
 

h2. Date de iesire

Pe prima linie a fisierului $polig.out$ se afla un singur numar, numarul maxim de flori ce il poate vedea.

Pe un singur rand se va scrie solutia, costul maxim pentru poligonul convex cerut.

h2. Restrictii si precizari

h2. Restrictii

* $1 ≤ N ≤ 100$
* $-10000 ≤ x{~i~} ≤ 10000$
* $0 ≤ y{~i~} ≤ 10000$
* $0 ≤ c{~i~} ≤ 10000$
* Un poligon este convex daca nu contine un unghi cu masura strict mai mare decat 180 grade
* Oricare trei puncte sunt necoliniare si nu exista 2 puncte care sa fie coliniare cu originea
* Cel putin 20% din teste vor avea $N ≤ 15$

* $-10000$ <= x[i] <= $10000$
* $0$ <= y[i] <= $10000$
* $1$ <= n <= $100$

h2. Exemplu

table(example). |_. polig.in |_. polig.out |
| 7

table(example) |_. $polig.in$ |_. $polig.out$ |
|7

-14 12 14
4 10 5
6 14 20

-8 13 16
-2 11 14
-4 11 1

| 50
|

|50|

h3. Explicatie

Lucy porneste din coordonata $0, 0$, apoi viziteaza gradinile $3$, $5$ si $1$ in aceasta ordine si se intoarce la coordonata $0, 0$.

Poligonul maxim se face folosind punctele $3$, $5$ , $1$ , in aceasta ordine.

== include(page="template/taskfooter" task_id="polig") ==

2162