== include(page="template/taskheader" task_id="bcrc") ==
Poveste si cerinta...
Gigel se afla intr-un labirint alcatuit din $N$ camere, numerotate de la $1$ la $N$, asezate in cerc. Din camera $K$ ({$1 < K < N$}) el poate trece in camerele $K - 1$ si $K + 1$. Din camera $1$ poate trece in camerele $2$ si $N$, iar din camera $N$ poate trece in camerele $N - 1$ si $1$.
Initial (la momentul de timp $0$), Gigel se afla in camera $1$. In fiecare moment de timp, Gigel poate decide sa ramana in camera in care se afla sau sa se mute intr-una din cele $2$ camere invecinate. Deplasarea dintr-o camera intr-una din camerele invecinate dureaza o unitate de timp. Astfel, daca la momentul $T$ Gigel decide sa se deplaseze intr-o camera vecina, el va ajunge in camera respectiva la momentul $T + 1$.
Din cand in cand, in unele camere apar cutii continand fiecare un anumit numar de bomboane (posibil diferit de la o cutie la alta). Sa presupunem ca o cutie apare in camera $X$ la momentul de timp $T$. Daca Gigel se afla la momentul $T$ in camera $X$ (sau intra in acea camera chiar la momentul $T$), atunci el ia cutia si mananca toate bomboanele din ea. In caz contrar, Gigel nu va putea manca nici o bomboana din cutie, deoarece aceasta va disparea pana la momentul $T + 1$.
h2. Cerinta
Cunoscand numarul de camere din labirint si momentele de timp la care apar cutiile cu bomboane, determinati care este numarul maxim de bomboane pe care le poate manca Gigel. Numarul de bomboane pe care le mananca Gigel este suma numerelor de bomboane din fiecare cutie pe care o ia.
h2. Date de intrare
...
Prima linie a fisierului $bcrc.in$ contine doua numere intregi, separate printr-un spatiu: $N$ si $M$, reprezentand numarul de camere din labirint, respectiv numarul de cutii. Fiecare din urmatoarele $M$ linii contine cate 3 numere intregi, separate prin cate un spatiu: $T$, $C$ si $B$. $T$ reprezinta momentul la care apare cutia. $C$ reprezinta numarul camerei in care apare cutia. $B$ reprezinta numarul de bomboane pe care le contine cutia.
Cutiile sunt date in fisierul de intrare in ordine *crescatoare* a momentelor de timp la care apar.
h2. Date de iesire
...
In fisierul $bcrc.out$ veti afisa un singur numar, reprezentand numarul maxim de bomboane pe care le poate manca Gigel.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 2 048$
* $0 ≤ M ≤ 50 000$
* Pentru fiecare cutie:
** $1 ≤ T ≤ 1 000 000 000$
** $1 ≤ C ≤ N$
** $1 ≤ B ≤ 9 999$
* Pot aparea mai multe cutii la acelasi moment de timp, in camere diferite (dar nu in acelasi moment de timp si in aceeasi camera)
* $30%$ din fisierele de test vor avea $M ≤ 5 000$
* $30%$ din fisierele de test vor avea $N ≤ 256$
h2. Exemplu
table(example). |_. bcrc.in |_. bcrc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8 4
2 7 9
3 5 999
10 2 12
10 1 10
| 21
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="bcrc") ==
