venus

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$ ore, indiferent de complexitatea acesteia (mai exact, dacă Vasile începe să lucreze la comandă în momentul $x$, la momentul $x+T$ ore 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 venus.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
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, iar ora este un număr natural cuprins între $0$ şi $23$. 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 venus.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 și precizări

• $1 \leq N \leq 1 \ 000$;
• $1 \leq T \leq 500$;
• $1 \leq V \leq 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ă $50\%$ din punctajul pentru fiecare test pentru determinarea valorii pmin. Punctajul integral pentru fiecare test se acordă pentru rezolvarea ambelor cerinţe (pmin şi o planificare optimală).

Exemplu

venus.in

4 25
90 10 ianuarie 20
50 2 ianuarie 8
20 4 ianuarie 3
70 2 ianuarie 9 

venus.out

50
4 1 3 2

Explicație

• Începând cu 1 ianuarie ora 0, Vasile execută comanda $4$ şi termină pe 2 ianuarie la ora 1.00.
• Execută apoi comanda $1$ pe care o termină pe 3 ianuarie la ora 2.00.
• Execută apoi comanda $3$ pe care o termină pe 4 ianuarie la ora 3.00.
• Execută apoi comanda $2$ pe care o termină pe 5 ianuarie la ora 4.00, ceea ce înseamnă că a depăşit termenul de predare, deci pierde valoarea ei ($50$).

Există şi alte planificări optimale posibile. De exemplu, 4 3 1 2.