teme

Teme

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

Eşti student la Facultatea de Informatică. Ai $n$ ani de studiu. În fiecare an de studiu, ai de făcut un anumit număr $m$ teme (numărul de teme din fiecare an nu e neapărat acelaşi în fiecare an). A $i$-a temă din anul al $j$-lea durează $t_{i,j}$ unităţi de timp. Din păcate, ea trebuie predată după cel mult $d_{i,j}$ unităţi de timp de la începutul anului universitar. Fiind student, nu poţi să lucrezi decât la o temă în acelaşi timp. Dacă începi a $i$-a temă la $t$ unităţi de timp după începutul anului universitar, o termini după $t + t_{i,j}$ unităţi de timp. Dacă $t + t_{i,j} > d_{i,j}$, vei preda tema după ce deadline-ul a expirat. Profesorul care a dat tema respectivă este supărat dacă întârzii cu tema. Supărarea lui este egală cu timpul cu care ai întârziat: $d_{i,j} - (t + t_{i,j})$. Scopul tău este să minimezi supărarea celui mai supărat profesor.

Eşti student la Facultatea de Informatică. Ai $n$ ani de studiu. În fiecare an de studiu, ai de făcut un anumit număr $m$ teme (numărul de teme din fiecare an nu e neapărat acelaşi în fiecare an). A $i$-a temă din anul al $j$-lea durează $t{~i,j~}$ unităţi de timp. Din păcate, ea trebuie predată după cel mult $d{~i,j~}$ unităţi de timp de la începutul anului universitar. Fiind student, nu poţi să lucrezi decât la o temă în acelaşi timp. Dacă începi a $i$-a temă la $t$ unităţi de timp după începutul anului universitar, o termini după $t + t{~i,j~}$ unităţi de timp. Dacă $t + t{~i,j~} > d{~i,j~}$, vei preda tema după ce deadline-ul a expirat. Profesorul care a dat tema respectivă este supărat dacă întârzii cu tema. Supărarea lui este egală cu timpul cu care ai întârziat: (t + t{~i,j~}) - $d{~i,j~}$. Scopul tău este să minimezi supărarea celui mai supărat profesor.

h2. Date de intrare

h2. Restricţii
* $1 ≤ n ≤ 100$

* $1 ≤ m ≤ 10000$

* $0 ≤ m ≤ 10000$
* un an de studiu este suficient de lung pentru a termina toate temele din anul respectiv (nu există riscul de a lucra la o temă din anul 1 în anul 2, etc)
* termenele limită şi duratele temelor sunt numere întregi între $1$ şi $10000$

h2. Exemplu

4 9
3 14
2 15

| 0

| 1

|
== include(page="template/taskfooter" task_id="teme") ==