Gardieni

gardieni

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

Seful unei companii de pe o planeta necunoscuta doreste ca sediul firmei 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 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 $t$ cuprins in intervalul inchis $[a,b]$ $(a ≤ t ≤ 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.

Poveste si cerinta...

h2. 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.

Fisierul de intrare $gardieni.in$ ...

h2. 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$.

In fisierul de iesire $gardieni.out$ ...

h2. Restrictii

* $1 ≤ N ≤ 50 005$
* $1 ≤ T ≤ 1 000 000$
* $1 ≤ a ≤ b ≤ T$
* $1 ≤ c ≤ 2^20^$
* Oricum am alege $11$ oferte ale firmelor de securitate si considerand intervalele asociate lor $[a{~1~},b{~1~}]$, $[a{~2~},b{~2~}]$ ... $[a{~11~},b{~11~}]$ nu exista un numar natural $x$ astfel incat $a{~1~} ≤ x ≤ b{~1~}$, $a{~2~} ≤ x ≤ b{~2~}$ ..., $a{~11~} ≤ x ≤ b{~11~}$.
* Sa garanteaza ca in fiecare moment de timp exista cel putin un paznic care poate fi angajat

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. gardieni.in |_. gardieni.out |

| 3 5
  2 4 3
  1 3 1
  5 5 2
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Pentru momentele de timp $1$, $2$ si $3$ se va angaja cate un paznic de la a doua firma si se va plati in total $1+1+1=3$. Pentru momentul $4$ se va alege un paznic de la prima 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. Costul total va fi $1+1+1+3+2=8$.

...

== include(page="template/taskfooter" task_id="gardieni") ==

2604