Möhtəşəm yarışlar

"Zibilçi ova çıxır" proqramlaşdırma yarışının iştirakçıları üçün bir yarış təşkil olunub. Yarışın başlanğıc və son nöqtələrinə əlavə olaraq, ziyarət edilə bilən n (n ≤ 20) digər yerlər də mövcuddur. Hər bir i (1 ≤ i ≤ n) yerində bir tapşırıq var və bu tapşırıq sizə p[i] xal qazandıracaq. Tapşırığın yerinə yetirilməsi t[i] dəqiqə tələb edir. Hər bir tapşırıq yalnız bir dəfə yerinə yetirilə bilər, yəni iştirakçı eyni yerə bir dəfədən çox qayıda bilməz. Yarış başladıqdan sonra başlanğıc nöqtəsinə qayıtmaq olmaz və yarış son nöqtəyə çatdıqda başa çatır.

Yarış t dəqiqə ərzində tamamlanmalıdır. Yəni başlanğıc və son nöqtəyə çatma vaxtı t dəqiqəni keçməməlidir. Bundan əlavə, bəzi tapşırıqların d[i] son tarixi var, yəni tapşırıq başlanğıc nöqtəsindən çıxdıqdan sonra d[i] dəqiqədən gec olmayaraq yerinə yetirilməlidir. İştirakçı i yerinə çatarsa, i nöqtəsindəki tapşırıq mütləq yerinə yetirilməlidir. İştirakçı yerə gec çatırsa və tapşırığı son tarixə qədər yerinə yetirə bilmirsə, o zaman ümumiyyətlə bu yerə daxil olmaq hüququ yoxdur.

Tapşırıqların yerinə yetirilməsindən əldə edilə biləcək maksimum xal sayını tapın.

Giriş məlumatları

Birinci sətir iki natural ədəd n və t (t ≤ 1440) ehtiva edir. Növbəti n sətirin hər biri üç tam ədəd p[i] (1 ≤ p[i] ≤ 100), t[i] (1 ≤ t[i] ≤ 1440) və d[i] (-1 ≤ d[i] ≤ 1440) ehtiva edir. Əgər d[i] = -1-dirsə, o zaman i-ci tapşırığın yerinə yetirilməsi üçün son tarix mövcud deyil. Son n + 2 sətir n + 2 qeyri-mənfi tam ədəd ehtiva edir. i-ci sətirdə və j-ci sütunda olan ədəd, i yerindən j yerinə getmək üçün tələb olunan dəqiqə sayını (≤ 1440) göstərir. Başlanğıc və son nöqtələrin indeksləri müvafiq olaraq n + 1 və n + 2-dir.

Zəmanət verilir ki, hər bir yerə özündən getmə vaxtı 0-a bərabərdir, lakin iki nöqtə arasında səyahət vaxtı fərqli istiqamətlərdə fərqli ola bilər (bir istiqamətdə qalxma, digər istiqamətdə isə enmə ola bilər).

Çıxış məlumatları

Birinci sətirdə yarışlarda qazanıla biləcək maksimum xal sayını çıxarın. İkinci sətirdə bu maksimuma çatmaq üçün yerinə yetirilməli olan tapşırıqların indekslərinin siyahısını çıxarın. İndeksləri bir boşluqla ayırın. Əgər maksimum bir neçə tapşırıq dəstində əldə edilirsə, leksikoqrafik olaraq ən kiçiyini çıxarın. Yəni, əgər eyni maksimum iki dəstdə əldə edilirsə, dəstdəki ilk tapşırığın indeksi ən kiçik olmalıdır. Əgər dəstlərdəki ilk indekslər bərabərdirsə, o zaman ikinci indeksin ən kiçik olduğu dəsti seçmək lazımdır və s.

Əgər maksimum xal sayı 0-a bərabərdirsə, o zaman ikinci sətirdə tapşırıqların indeksləri əvəzinə boş sətir çıxarın.