Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

Debesys

Moover yra IT kompanija, kuri specializuojasi intestuotojų pinigų švaistyme. Neseniai Moover nusprendė perkelti visą savo infrastruktūrą į debesis. Kompanija nuomosis procesorius n dienų iš eilės, ir kiekvieną dieną reikia išsinuomuoti k procesorių.

Serverius nuomojanti kompanija siūlo n planų, iš kurių kiekvienas yra aprašomas keturiais parametrais:

  • s_i ir e_i - pirma ir paskutinė dienos (imtinai) kuriomis galioja šis planas.
  • c_i - kiek daugiausiai procesorių galima išsinuomuoti per dieną naudojant šitą planą.
  • p_i - kiek kainuoja vieno procesoriaus nuoma vienai dienai.

Moover kiekvieną dieną gali nuomotis kiek nori procesorių iš kurių nori tą dieną galiojančių planų. Taip pat pagal kiekvieną planą nuomojamas procesorių kiekis gali kisti kiekvieną dieną.

Kiekvieną dieną Moover nuomosis k pigiausių procesorių iš tą dieną galiojančių planų. Jei kažkurią dieną neįmanoma išsinuomoti k procesorių, tai Moover turės išsitekti su mažiau procesorių nei numatyta, ir nuomosis visus tą dieną galimus procesorius.

Pradiniai duomenys

Pirmoje eilutėje yra trys skaičiai n, k, ir m - dienų skaičius, norimas procesorių skaičius per dieną, ir planų skaičius (1\\leqn,k\\leq10^6,1\\leqm\\leq2\\times10^5).

Sekančiose m eilučių yra pateikti planai, po keturis skaičius kiekvienoje eilutėje: s_i,e_i,c_i,p_i - atitinkamai pirma plano diena, paskutinė plano diena, procesorių skaičius, ir procesoriaus kaina (1\\leqs_i\\leqe_i\\leqn,1\\leqc_i,p_i\\leq10^6).

Rezultatai

Išveskite vieną skaičių - kiek pinigų iš viso Moover sumokės už procesorių nuomą.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1
 
44
 
Pirmą dieną Moover nuomosis 5 procesorius iš antro plano, ir 2 procesorius iš pirmo plano.
Likusias 4 dienas Moover naudosis tik trečiuoju planu.
 
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8
 
462
 








4 100 3
3 3 2 5
1 1 3 2
2 4 4 4




64