Hoata

Hoața

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

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 &le; i &le; N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare <tex> ${v}_{i}$ </tex> şi greutate <tex> ${g}_{i}$ </tex>. În prima cameră intră $K$ hoţi, fiecare având în spinare câte un rucsac de capacitate $G$, iniţial gol. Când un hoţ se află în camera $i$, acesta poate sustrage oricâte lingouri din camera curentă şi să le adauge în rucsacul său, cu condiţia ca suma greutăţilor lingourilor din rucsac să nu depăşească $G$. Un lingou o dată furat, acesta va rămâne în rucsacul hoţului până la ieşirea din muzeu.

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 ≤ i ≤ N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare $v{~i~}$ şi greutate $g{~i~}$. În prima cameră intră $K$ hoţi, fiecare având în spinare câte un rucsac de capacitate $G$, iniţial gol. Când un hoţ se află în camera $i$, acesta poate sustrage oricâte lingouri din camera curentă şi să le adauge în rucsacul său, cu condiţia ca suma greutăţilor lingourilor din rucsac să nu depăşească $G$. Un lingou o dată furat, acesta va rămâne în rucsacul hoţului până la ieşirea din muzeu.

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 &le; i &le; N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 &le; i &le; N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare <tex> ${x}_{i}$ </tex>. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin <tex> ${x}_{i} + 1$ </tex> hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 ≤ i ≤ N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 ≤ i ≤ N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare $x{~i~}$. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin $x{~i~}$ hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

Odată ieşiţi din muzeu, hoţii calculează captura totală ca fiind suma valorilor $v$ corespunzătoare lingourilor din cele $K$ rucsacuri. Se dau $T$ scenarii, şi pentru fiecare se cere captura maximă posibilă în condiţiile date, sau $−1$ dacă orice s-ar întâmpla hoţii ar fi prinşi.
h2. Date de intrare

Prima linie conţine un singur număr natural $T$, reprezentând numărul de scenarii. Urmează descrierile celor $T$ scenarii. Descrierea unui scenariu se face după cum urmează: pe prima linie trei numere naturale $N$, $K$, $G$, separate prin spaţii; pe următoarele $N$ linii câte trei numere naturale, unde pe linia $1 &le; i &le; N$ se află numerele <tex> ${v}_{i}$, ${g}_{i}$, ${x}_{i}$ </tex> separate prin spaţii.

Prima linie conţine un singur număr natural $T$, reprezentând numărul de scenarii. Urmează descrierile celor $T$ scenarii. Descrierea unui scenariu se face după cum urmează: pe prima linie trei numere naturale $N$, $K$, $G$, separate prin spaţii; pe următoarele $N$ linii câte trei numere naturale, unde pe linia $1 ≤ i ≤ N$ se află numerele $v{~i~}, g{~i~}, x{~i~}$ separate prin spaţii.

h2. Date de ieşire

* $1 ≤ $N$ ≤ 300$
* $1 ≤ $K$ ≤ 50$
* $1 ≤ $G$ ≤ 300$

* $1$ &le; <tex> ${v}_{i}$ </tex> &le; $300$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${g}_{i}$ </tex> &le; $300$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${x}_{i}$ </tex> &le; $50$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${S}_{N}$ </tex> &le; $900$, unde cu <tex> ${S}_{N}$ </tex> am notat suma valorilor $N$ corespunzătoare celor $T$ scenarii.
 
table(subtasks). |_. # |_. Punctaj |_. Restricţii |
| 1
2
3
4
| 11
18
40
31
| 1
2
3
4

* $1 ≤ v{~i~} ≤ 300$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ g{~i~} ≤ 300$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ x{~i~} ≤ 50$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ S{~N~} ≤ 900$, unde cu $S{~N~}$ am notat suma valorilor $N$ corespunzătoare celor $T$ scenarii.
 
|_. # |_. Punctaj |_. Restricţii |
| $1$
$2$
$3$
$4$
| $11$
$18$
$40$
$31$
| $N ≤ 4, K ≤ 3, G ≤ 7, S{~N~} ≤ 12, v{~i~} ≤ 20, 2 ≤ g{~i~} ≤ 7, x{~i~} ≤ 3$, oricare ar fi $1 ≤ i ≤ N$.
Există $1 ≤ j ≤ N$ astfel încât $x{~i~} = K$ oricare ar fi $1 ≤ i ≤ N$, $i$ ≠ $j$.
$N ≤ 40, G ≤ 40, S{~N~} ≤ 120, v{~i~} ≤ 40, g{~i~} ≤ 40$, oricare ar fi $1 ≤ i ≤ N$.
Fără restricţii suplimentare.

|
h2. Exemplu

**Primul scenariu**

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află o rezervă infinită de lingouri de aur de valoare $10$ şi greutate $2$, iar în camera $2$ se află o rezervă infinită de lingouri de aur de valoare $9$ şi greutate $1$. Alarma dintre camera $1$ şi camera $2$ are <tex> ${x}_{1}$ </tex> = $1$, iar alarma dintre camera $2$ şi ieşire are <tex> ${x}_{1}$ </tex> = $2$. În condiţiile date alarmele nu vor suna indiferent ce alege să facă hoţul, aşa că acesta poate obţine o captura maximă de $27 = 9 + 9 + 9$ furând trei lingouri din camera $2$.

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află o rezervă infinită de lingouri de aur de valoare $10$ şi greutate $2$, iar în camera $2$ se află o rezervă infinită de lingouri de aur de valoare $9$ şi greutate $1$. Alarma dintre camera $1$ şi camera $2$ are $x{~1~} = 1$, iar alarma dintre camera $2$ şi ieşire are $x{~2~} = 2$. În condiţiile date alarmele nu vor suna indiferent ce alege să facă hoţul, aşa că acesta poate obţine o captura maximă de $27 = 9 + 9 + 9$ furând trei lingouri din camera $2$.

**Al doilea scenariu**