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

_După rezultatele recente, Semicerc a intrat în pământ de ruşine... aşa că s-a decis sa îşi deschidă un restaurant împreună cu Giotozila care strânge bani pentru un coş de gunoi mai rezistent._

_După rezultatele recente, Semicerc a intrat în pământ de ruşine... aşa că s-a decis să îşi deschidă un restaurant împreună cu Giotozila care strânge bani pentru un coş de gunoi mai rezistent._

Ca orice -_bişniţă_- afacere, să deţii un restaurant nu este uşor. Trebuie să ai grijă ca ingredientele să fie mereu prezente în frigidere ca să poţi satisface cât mai mulţi clienţi (implicit să faci cât mai mulţi bani). De asemenea, trebuie să ai grijă ca ingredientele să fie mereu proaspete ca să nu fi responsabil pentru toxinfecţii alimentare sau alte boli.

În această lume fictivă, ziua durează $N$ ore şi în fiecare oră vine un client căruia îi cunoşti felul de mâncare pe care îl va comanda. Meniul acestui restaurant contine $K$ feluri de mâncare. Considerăm că fiecare fel de mâncare este alcătuit dintr-un singur ingredient. Fiecare ingredient este definit de $cost$, $profit$ şi $rezistenţă$. Costul unui ingredient este suma de bani plătită pentru a cumpăra o unitate dintr-un anumit ingredient, profitul este suma de bani câştigată daca vinzi felul de mâncare corespunzător unui ingredient, iar rezistenţa reprezintă numărul de ore în care ingredientul este proaspăt.

În această lume fictivă, ziua durează $N$ ore şi în fiecare oră vine un client căruia îi cunoşti felul de mâncare pe care îl va comanda. Meniul acestui restaurant conţine $K$ feluri de mâncare. Considerăm că fiecare fel de mâncare este alcătuit dintr-un singur ingredient. Fiecare ingredient este definit de $cost$, $profit$ şi $rezistenţă$. Costul unui ingredient este suma de bani plătită pentru a cumpăra o unitate dintr-un anumit ingredient, profitul este suma de bani câştigată dacă vinzi felul de mâncare corespunzător unui ingredient, iar rezistenţa reprezintă numărul de ore în care ingredientul este proaspăt.

Pentru procura ingredientelor, restaurantul deţine un blatmobil care vine din $t$ în $t$ secunde începând de la ora 0, deci în momentele $0, t, 2 * t, 3 * t, 4 * t, ..., q * t unde q * t < N$. Acesta vine cu ingrediente proaspete de la non-stop, mai exact cu $x{~1~}$ unităţi din primul ingredient, $x{~2~}$ unităţi din al doilea ingredient, ..., $x{~K~}$ din al K-ulea ingredient. Astfel, de fiecare dată când vine blatmobilul, patronii trebuie să plătească $x{~1~} * cost{~1~} + x{~2~} * cost{~2~} + ... + x{~K~} * cost{~K~}$ $JC$ "({$Junior Coins$})":https://www.infoarena.ro/problema/bitconnect. Din motive sanitare, ingredientele care erau înainte în frigider vor fi aruncate la gunoi.

* $0 ≤ x{~i~} ≤ N; 1 ≤ i ≤ K$
* $Un aliment adus la momentul i poate fi utilizat pentru a satisface orice client care vine la restaurant în momentele din intervalul [i, i + min(t, rezistenţă{~aliment~}))$
* $În caz că există mai multe soluţii care aduc profitul maxim, se poate afişa orice soluţie.$

* $Subtask **{%{color:#4C7D63}Rotten (Dosar +penal+ pentru încălcarea normelor sanitare)%}** - 10 puncte: N * K ≤ 100$
* $Subtask **{%{color:red}Raw (Toxinfecţie alimentară)%}** - 15 puncte: N * K ≤ 500, N ≤ 100$
* $Subtask **Burnt (Dezgustător)** - 15 puncte: N * K ≤ 2 * 10^4^, N ≤ 4000$
* $Subtask **{%{color:#875D48}Well done (aproape OK, să zicem)%}** - 30 puncte: N * K ≤ 2 * 10^5$
* $Subtask **{%{color:#BA5353}Medium rare (Perfect)%}** - 30 puncte: N * K ≤ 2 * 10^6$

* $Subtask **{%{color:#4C7D63}Rotten (Dosar +penal+ pentru încălcarea normelor sanitare)%}** - 10 puncte (testele 1-2): N * K ≤ 100$
* $Subtask **{%{color:red}Raw (Toxiinfecţie alimentară)%}** - 15 puncte (testele 3-5): N * K ≤ 500, N ≤ 100$
* $Subtask **Burnt (Dezgustător)** - 15 puncte (testele 6-8): N * K ≤ 2 * 10^4^, N ≤ 4000$
* $Subtask **{%{color:#875D48}Well done (aproape OK, să zicem)%}** - 30 puncte (testele 9-14): N * K ≤ 2 * 10^5$
* $Subtask **{%{color:#BA5353}Medium rare (Perfect)%}** - 30 puncte (testele 15-20): N * K ≤ 2 * 10^6$

h2. Exemplu