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ța

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 ≤ N ≤ 1000
• 1 ≤ T ≤ 500
• 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ă 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.