Fişierul intrare/ieşire:	rompetrol.in, rompetrol.out	Sursă	Autumn Warmup 2007, Runda 2
Autor	Mugurel Ionut Andreica	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	1.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rompetrol

Firma Rompetrol are N benzinarii amplasate de-a lungul autostrazii Soarelui. Pozitiile benzinariilor sunt cunoscute, fiind specificate prin distantele d₁, d₂, ... , d_N ( d_i reprezinta distanta de la sediul firmei Rompetrol pana la benzinaria i). Sediul firmei Rompetrol este amplasat la intrarea pe autostrada Soarelui. De asemenea, pentru fiecare benzinarie se cunoaste cantitatea de combustibil c_i necesara pentru a satisface cerintele clientilor ce utilizeaza benzinaria respectiva. In K dintre aceste benzinarii firma doreste sa amenajeze depozite de combustibil, care sa alimenteze benzinaria respectiva, precum si, posibil, alte benzinarii invecinate. Fiecare benzinarie va fi alimentata de la depozitul cel mai apropiat. Pentru fiecare benzinarie se cunoaste costul a_i ce trebuie platit pentru amenajarea unui depozit de combustibil in cadrul benzinariei. Costul de transport al benzinei de la un depozit X la o benzinarie Y este egal cu produsul dintre cantitatea de combustibil necesara la benzinaria Y si distanta dintre X si Y. Costul de transport pentru o amplasare a depozitelor data va fi egal cu suma costurilor de transport ale tuturor benzinariilor. Costul total este egal cu suma dintre costul total de transport si costurile de amenajare ale depozitelor in K dintre benzinarii.

Cerinta

Scrieti un program care sa determine costul total minim.

Date de intrare

Fisierul de intrare rompetrol.in contine pe prima linie doua numere naturale separate prin spatiu N si K, reprezentand numarul de benzinarii si respectiv numarul de depozite care trebuie construite. Pe fiecare linie i din urmatoarele N sunt scrise 3 numere naturale, separate prin cate un spatiu: d_i, c_i si a_i, reprezentand distanta de la benzinaria i la sediul firmei Rompetrol, cantitatea de combustibil necesara la benzinaria i si costul amenajarii unui depozit in benzinaria i.

Date de iesire

Fisierul de iesire rompetrol.out va contine pe prima linie costul total minim posibil.

Restrictii

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ N
• 1 ≤ N*K ≤ 5 000 000
• 1 ≤ d₁ < d₂ < ... < d_N ≤ 10 000 000
• 1 ≤ c_i ≤ 1000
• 0 ≤ a_i ≤ 1 000 000 000
• Cel putin 40% din teste vor avea N ≤ 500 si K ≤ 300

Exemplu

Explicatie

Depozitul 1 va fi construit in benzinaria 2 si alimenteaza benzinariile 1, 2, 3. (Cost: 1*1+0*1+6*1=7)
Depozitul 2 va fi construit in benzinaria 4 si alimenteaza benzinariile 4, 5. (Cost: 0*1+1*1=1)
Depozitul 3 va fi construit in benzinaria 6 si alimenteaza benzinaria 6. (Cost: 0*1).
Costul total de transport este 7+1+0. Costul amplasarii celor 3 benzinarii este 0+0+0=0. Costul total este 8+0=8.

Cum se trimit solutii?