Binary Robbery

Cerință

Un hacker pe nume Marius încearcă să spargă baza de date secretă a Colegiului Național „Mihai Eminescu”. Baza de date este împărțită în mai multe tipuri de porțiuni de date.

Fiecare tip de date este caracterizat prin:

• dimensiunea unei porțiuni (spațiul ocupat)
• valoarea obținută pentru fiecare porțiune furată
• numărul maxim de porțiuni disponibile.

Hackerul dispune de un dispozitiv cu o capacitate limitată de stocare de $C$ unități.

Se dă un parametru $T$.

• Dacă $T = 1$, se cere să se determine dacă hackerul poate fura date astfel încât să ocupe exact $C$ unități de memorie.
• Dacă $T = 2$, se cere să se determine valoarea maximă totală care poate fi obținută fără a depăși capacitatea $C$.

Date de intrare

Fișierul de intrare binaryrobbery.in conține:

Pe prima linie, un număr întreg $T$ ($1$ sau $2$).
Pe a doua linie, două numere întregi $N$ și $C$, reprezentând:

• $N$ – numărul de tipuri de date,
• $C$ – capacitatea dispozitivului.

Pe următoarele N linii se află câte trei numere întregi $d$, $v$, $f$, unde:

• $d$ = dimensiunea unei porțiuni,
• $v$ = valoarea unei porțiuni,
• $f$ = numărul maxim de porțiuni disponibile.

Date de ieșire

Fișierul de ieșire binaryrobbery.out va conține:

• Dacă $T = 1$, se va afișa DA sau NU.
• Dacă $T = 2$, se va afișa un singur număr întreg, reprezentând valoarea maximă.

Restricții și precizări

• $1 ≤ N ≤ 1 \ 000$
• $1 ≤ C ≤ 10 \ 000$
• $1 ≤ d, v ≤ 10 \ 000$
• $1 ≤ f ≤ 1 \ 000 \ 000$

Exemplul 1

binary-robbery.in

1
2 7
3 10 2
2 5 3

binary-robbery.out

DA

Exemplul 2

binary-robbery.in

2
2 7
3 10 2
2 5 3

binary-robbery.out

20

Explicație

Se pot alege:

• o porțiune de dimensiune $3$, cu valoarea $10$;
• două porțiuni de dimensiune $2$, fiecare cu valoarea $5$.

Dimensiunea totală este $7$, iar valoarea totală este $20$.