Fișierul intrare/ieșire	venus1.in, venus1.out	Sursă	ONI 2019 clasa a 7-a
Autor	Emanuela Cerchez	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.25 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Venus1 (baraj gimnaziu)

Notă: aceasta este problema venus cu granularitate de secunde în loc de ore. Astfel limitele se măresc.

Casa de Modă Venus a decis să se modernizeze și, începând cu 1 ianuarie 2020 ora 00:00, l-a angajat pe robotul Vasile. Vasile poate executa orice comandă în exact T secunde, indiferent de complexitatea acesteia (mai exact, dacă Vasile începe să lucreze la comandă în momentul x, la momentul x + T secunde comanda va fi gata de predare). Foarte încrezătoare în calitățile robotului Vasile, Casa de Modă Venus a lansat o campanie publicitară cu sloganul “Dacă am întârziat, primești produsul comandat gratis!”. Campania și-a atins scopul, ca urmare Casa de Modă a primit deja N comenzi pentru întreg anul 2020. Pentru fiecare comandă sunt specificate valoarea acesteia, precum și data și ora până la care produsul comandat trebuie să fie gata de predare. Dacă Vasile predă produsul exact la data și ora specificată în comandă (sau înainte) el încasează valoarea comenzii. Dacă nu, el tot trebuie să execute comanda respectivă, dar nu va primi suma reprezentând valoarea ei.

Deși lucrează fără nicio pauză, Vasile estimează că este posibil să nu poată preda la timp toate comenzile, dar își planifică lucrul, astfel încât pierderea să fie minimă (adică suma valorilor comenzilor care nu vor fi predate la timp să fie cât mai mică). Numim planificare optimală succesiunea în care Vasile trebuie să execute cele N comenzi, astfel încât pierderea să fie minimă.

Cerință

Scrieți un program care, cunoscând informațiile referitoare la cele N comenzi, determină pierderea minimă, precum și o planificare optimală.

Date de intrare

Fișierul de intrare venus1.in conține pe prima linie numărul natural N, reprezentând numărul de comenzi și numărul natural T, reprezentând numărul de ore necesare lui Vasile pentru a executa o comandă. Pe următoarele N linii se află informațiile despre comenzi, câte o comandă pe o linie, sub forma:

V zi luna ora minut secunda

unde V este valoarea comenzii, zi este ziua în care trebuie predată comanda (un număr natural cuprins între 1 și numărul de zile ale lunii), luna este denumirea lunii, ora este un număr natural cuprins între 0 și 23, iar minut și secunda sunt numere cuprinse între 0 și 59. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu. Comenzile se consideră numerotate de la 1 la N în ordinea din fișierul de intrare.

Date de ieșire

Fișierul de ieșire venus1.out va conține pe prima linie numărul natural pmin, reprezentând pierderea minimă. Pe a doua linie vor fi scrise N numere naturale distincte cuprinse între 1 și N, separate prin câte un spațiu, reprezentând o planificare optimală.

Restricții

• 1 ≤ N ≤ 200 000
• 1 ≤ T ≤ 15 000
• 1 ≤ V ≤ 10 000
• Numele lunilor vor fi scrise cu litere mici.
• Anul 2020 este an bisect, adică luna februarie are 29 de zile.
• Dacă există mai multe planificări optimale, se va accepta orice soluție corectă.
• Se acordă 2p pentru fiecare test pentru determinarea valorii pmin. Punctajul integral de 5p pentru fiecare test se acordă pentru rezolvarea ambelor cerințe (pmin și o planificare optimală).

Exemplu