Dispetçer
Klanın ninjaları müştəriyə göndərilir və gördükləri işə görə mükafatlandırılırlar.
Klanın bir ustad ninjası var. Ustad istisna olmaqla, hər bir ninjanın dəqiq bir rəhbəri mövcuddur. Məxfilik və liderliyi qorumaq üçün bütün tapşırıq təlimatları yalnız rəhbər tərəfindən öz tabeçiliyində olanlara çatdırılır. Başqa üsullarla təlimatların ötürülməsi qadağandır.
Müəyyən sayda ninjanı toplayıb müştəriyə göndərmək istəyirsiniz. Göndərilən hər bir ninjaya görə ödəniş etməlisiniz. Hər bir ninjanın ödənişi sabitdir və ümumi ödəniş büdcəyə uyğun olmalıdır. Bundan əlavə, göndərilən ninjalara təlimatları çatdırmaq üçün bir ninjanı menecer kimi seçməlisiniz ki, o, hamısına təlimat göndərə bilsin. Seçilməyən ninjalar mesajları ötürə bilər. Menecer mütləq müştəriyə göndərilməməlidir. Əgər menecer göndərilmirsə, ona ödəniş etmək lazım deyil.
Büdcə daxilində qalaraq müştərinin məmnuniyyət səviyyəsini maksimuma çatdırmaq istəyirsiniz. Məmnuniyyət səviyyəsi göndərilən ninjaların ümumi sayı ilə menecerin liderlik səviyyəsinin hasilinə bərabərdir. Hər bir ninjanın liderlik səviyyəsi verilmişdir.
Hər bir ninjanın rəhbəri b[i], ödəniş miqdarı c[i], liderlik səviyyəsi l[i] (1 ≤ i ≤ n) və büdcə m verildikdə, müştərinin məmnuniyyət səviyyəsinin maksimum mümkün dəyərini çıxaran bir proqram yazın ki, menecer və göndərilən ninjalar elə seçilsin ki, bütün şərtlər yerinə yetirilsin.
Giriş məlumatları
Birinci sətir ninjaların sayı n (1 ≤ n ≤ 10^5) və büdcə m (1 ≤ m ≤ 10^9) verir. Növbəti n sətir hər bir ninjanın rəhbərini, maaşını və liderlik səviyyəsini təsvir edir. (i + 1) - ci sətir üç tam ədəd b[i], c[i], l[i] (0 ≤ b[i] < i, 1 ≤ c[i] ≤ m, 1 ≤ l[i] ≤ 10^9) verir ki, bu da i-ci ninjanın rəhbəri b[i], i-ci ninjanın maaşı c[i] və onun liderlik səviyyəsi l[i] deməkdir. i-ci ninja ustaddırsa, b[i] = 0. Həmişə b[i] < i bərabərsizliyi yerinə yetirildiyindən, hər bir ninjanın rəhbərinin nömrəsi həmişə öz nömrəsindən kiçikdir.
Çıxış məlumatları
Müştərinin məmnuniyyət səviyyəsinin maksimum mümkün dəyərini çıxarın.
Misal üçün qeyd
Əgər 1 nömrəli ninjanı menecer seçib 3, 4 nömrəli ninjaları müştəriyə göndərsəniz, ümumi ödəniş 4 olacaq və büdcəni aşmayacaq. Göndərilən ninjaların sayı 2 və menecerin liderlik səviyyəsi 3 olduğuna görə müştərinin məmnuniyyət səviyyəsi 6 olacaq. Bu, mümkün olan maksimum dəyərdir.