cercuri4

Cercuri4

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

Plictisit ingrozitor la cursul de geometrie, Bogdanel se apuca de desenat cercuri. In continuare, el vrea sa alega un numar oarecare de cercuri - fie acestea C1, C2 ... Ck - astfel incat Ci+1 este inclus in Ci, pentru 1 ≤ i ≤ k-1. Mai mult, pentru ca nu toate cercurile i-au iesit perfect, el le-a asocitat fiecaruia un grad de frumusete - F[i]. Curios din fire, Bogdanel vrea sa aleaga cercurile astfel incat suma gradelor de frumusete ale acestora sa fie maxima.

Plictisit îngrozitor la cursul de geometrie, Bogdanel se apucă de desenat cercuri. În continuare, el vrea să alegă un număr oarecare de cercuri - fie acestea $C1$, $C2$ ... $Ck$ - astfel încât $Ci+1$ este inclus in $Ci$, pentru $1 ≤ i ≤ k-1$. Mai mult, pentru că nu toate cercurile i-au ieşit perfect, el le-a asocitat fiecăruia un grad de frumuseţe - $F[i]$. Curios din fire, Bogdănel vrea să aleagă cercurile astfel incât suma gradelor de frumuseţe ale acestora sa fie maximă.

h2. Date de intrare

Fişierul de intrare $cercuri4.in$ contine pe prima linie un numar intreg N, reprezentand numarul de cercuri desenate. Urmeaza apoi N linii continand 4 numere intregi - X[i], Y[i], R[i], F[i], reprezentant coordonatele centrului, raza cercului, respectiv gradul de frumusete.

Fişierul de intrare $cercuri4.in$ conţine pe prima linie un număr întreg $N$, reprezentând numărul de cercuri desenate. Urmează apoi $N$ linii conţinând 4 numere întregi - $X[i]$, $Y[i]$, $R[i]$, $F[i]$, reprezentând coordonatele centrului, raza cercului, respectiv gradul de frumuseţe.

h2. Date de ieşire

În fişierul de ieşire $cercuri4.out$ se va afla un singur numar intreg, reprezentand suma gradelor de frumusete ale cerculilor alese.

În fişierul de ieşire $cercuri4.out$ se va afla un singur număr întreg, reprezentând suma gradelor de frumuseţe ale cerculilor alese.

h2. Restricţii
* $N ≤ 3000$
* $X[i], Y[i], R[i] ≤ 100000000$

* $F[i] <= 50 000$

* $F[i] ≤ 50 000$

h2. Exemplu
table(example). |_. cercuri4.in |_. cercuri4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
1 1 4 1
1 1 1 2
1 2 1 4
10 12 14 2
| 5

|

h3. Explicaţie
 
...

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

7948