Fişierul intrare/ieşire:	teme.in, teme.out	Sursă	ACM ICPC Faza Nationala 2015
Autor	Stefan Ciobaca	Adăugată de	ONIS2015 •ONIS2015
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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: (t + t_i,j) - d_i,j. Scopul tău este să minimezi supărarea celui mai supărat profesor.

Date de intrare

Fişierul de intrare teme.in conţine pe prima linie numărul de ani de studiu. Urmează datele de intrare pentru fiecare dintre cei n ani. Pentru un an, fişierul de intrare conţine numărul m de teme; pentru fiecare dintre cele m teme fişierul conţine două numere: durata temei şi deadline-ul la care trebuie predată.

Date de ieşire

În fişierul de ieşire teme.out afişează pentru fiecare an pe câte o linie supărarea celui mai supărat profesor, ţinând cont că ai grijă să faci temele astfel încât să minimizezi această supărare.

Restricţii

• 1 ≤ n ≤ 100
• 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

Exemplu

Cum se trimit solutii?