Fişierul intrare/ieşire:	gardieni.in, gardieni.out	Sursă	preONI 2008 Runda 3
Autor	Filip Cristian Buruiana	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Gardieni

Seful unei companii de pe o planeta necunoscuta doreste ca sediul sa fie pazit in fiecare moment intreg de timp de la 1 la T. El a primit N oferte de la firme de securitate de pe Terra de tipul a b c, avand semnificatia ca pentru pretul de c unitati poate fi angajat un paznic care sa pazeasca compania o unitate de timp, dar doar intr-un moment de timp cuprins in intervalul inchis [a,b] (a ≤ c ≤ b). Pe planeta unde se afla compania tehnologia nu este foarte avansata si de aceea este nevoie de ajutorul vostru pentru a afla costul minim care ar trebui sa il plateasca seful companiei astfel incat compania sa fie pazita in fiecare moment intreg de timp de la 1 la T. Bineinteles, pot fi angajati mai multi paznici de la aceiasi firma de securitate iar fiecare paznic angajat pazeste compania exact o singura unitate de timp.

Date de intrare

Fisierul de intrare gardieni.in contine pe prima linie doua numere naturale N si T avand semnificatia din enunt. Urmeaza apoi N linii care contin cate trei numere naturale a b c reprezentand ofertele fiecarei firme de securitate.

Date de iesire

In fisierul de iesire gardieni.out se afla pe prima linie numarl natural MIN, reprezentand costul minim care trebuie platit astfel incat compania sa fie pazita in fiecare moment intreg de timp de la 1 la T.

Restrictii

• 1 ≤ N ≤ 1000
• 1 ≤ T ≤ 1 000 000
• 1 ≤ a ≤ b ≤ T
• 1 ≤ c ≤ 2²⁰
• Oricum am alege 11 oferte ale firmelor de securitate si considerand intervalele asociate lor [a₁,b₁], [a₂,b₂] ... [a₁₁,b₁₁] nu exista un numar natural x astfel incat a₁ ≤ x ≤ b₁, a₂ ≤ x ≤ b₂ ... a₁₁ ≤ x ≤ b₁₁

Exemplu

Explicatie

Pentru momentele de timp 1, 2 si 3 se va angaja cate un paznic de la prima firma si se va plati in total 1+1+1=3, pentru momentul 4 se va alege un paznic de la a doua firma pentru costul de 3 unitati iar in momentul 5 se va alege un paznic de la a treia firma pentru costul de 2 unitati. 1+1+1+3+2=8

Cum se trimit solutii?