Državna razina / Primjena algoritama OŠ 2021. / Osnovna škola (8. razred) - 3. zadatak

Poradi Pandemije koronavirusa koja je svijet bacila na tjeme, uprava bazena Zora preporuča da se u bazenu nalazi manje od M ljudi.

Bazen je tijekom dana posjetilo N ljudi, a svaki je platio kartu za određen broj minuta. No, neki su ostali duže nego što su platili.

Uprava bazena odlučila im se djelomično smilovati te im od minuta provedenih u bazenu koje nisu platili na ulasku, na izlasku dodatno naplatiti samo one minute tijekom kojih je u bazenu bilo barem M ljudi.

Za svakog posjetitelja bazena ispiši koliko je ukupno minuta platio.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ N+1).

U sljedećih N redaka su po tri prirodna broja Di, Pi i Oi (1 ≤ Di, Pi, Oi ≤ 10^9), minuta na čijem je početku i-ta osoba došla u bazen, broj minuta koje je platila te broj minuta koje je ostala u bazenu.

Izlazni podaci

Za svaku osobu u zaseban redak ispiši koliko je ukupno minuta platila.

Primjer zadatka

Ulaz

2 2
1 1 3
2 1 3

Izlaz

3
2

Objašnjenje

Opis prvog probnog primjera: Prva osoba došla je na početku prve minute i ostala do kraja treće.

Druga osoba došla je na početku druge minute i ostala do kraja četvrte. Prva je osoba na ulasku platila samo prvu minutu, a druga osoba samo drugu minutu.

Tijekom druge i treće minute u bazenu je bilo M ljudi pa su one dodatno naplaćene prvoj osobi.

Drugoj je osobi dodatno naplaćena samo treća minuta, budući da je drugu minutu platila na ulasku. Četvrta minuta nije joj dodatno naplaćena, budući da u bazenu tada nije

bilo barem M ljudi.

Ulaz

3 3
2 1 4
1 1 4
3 1 4

Izlaz

3
3
2

Objašnjenje

Opis drugog probnog primjera: U trećoj i četvrtoj minuti u bazenu je bilo M ljudi te su one dodatno naplaćene prvoj i drugoj osobi. Trećoj je osobi dodatno naplaćena samo četvrta minuta.

Ulaz

3 2
2021 1 2
2021 2 2
2021 3 2

Izlaz

2
2
3

Objašnjenje

Opis trećeg probnog primjera: Treća je osoba platila tri, a ostala samo dvije minute u bazenu.