İnqrediyentlər#9674
Şef-aşpaz, Michelin ulduzu almağı hədəfləyən restoranın aşpazı olaraq, müfəttişləri öz imza yeməkləri ilə heyran etmək istəyir. Bunun üçün o, ümumi dəyər üçün maksimum büdcə B ayırıb və müfəttişlərə təqdim ediləcək yeməklərin ümumi prestijini maksimuma çatdırmağa çalışır.
Yeməklərin prestijini qiymətləndirmək üçün şef-aşpaz, onların dəyərini və tərkibini göstərən reseptlər siyahısı hazırlayır. Hər bir resept, əsas yeməyə tərkib əlavə edərək törəmə yemək əldə etməyi təsvir edir. Reseptdə əsas yeməyin dəyərindən əlavə tətbiq olunan reseptin dəyəri və əsas yeməyin prestijinə əlavə edilən prestij göstərilir. Şef-aşpaz prestiji öz vahidləri ilə ölçür, bunlar "prestij vahidləri" adlanır.
Məsələn, pizza hazırlamaq üçün reseptlər siyahısı belə ola bilər:
- pizza_tomato pizza_base tomato 1 2
- pizza_classic pizza_tomato cheese 5 5Burada pizza_base - heç bir reseptlə əlaqəli olmayan, o qədər sadə olan elementar yeməkdir ki, onun dəyəri əhəmiyyətsizdir (0 olaraq təyin edilir) və onun prestiji də 0-a bərabərdir. Şef-aşpaz, əsas yeməyə pizza_base pomidor əlavə edərək 1 avroya pizza_tomato törəmə yeməyi əldə edə bilər, 2 prestij vahidi qazanır. pizza_classic, pizza_tomato-ya pendir əlavə etməklə əldə edilir, əlavə 5 ödənişlə, əsas yeməyin prestijinə 5 prestij əlavə edilir; bu, pizza_classic-in ümumi dəyərinin 6, ümumi prestijinin isə 7 olduğunu göstərir.
İmza yeməyi seçimi, məsələn, həm pizza_tomato, həm də pizza_classic-i əhatə edə bilər. Belə bir seçim ümumi prestij 9 və ümumi dəyər 7 verəcəkdir. Reseptlər siyahısı və büdcə B ilə silahlanmış şef-aşpaz, Michelin müfəttişlərinə ümumi dəyəri B-dən çox olmayan, ümumi prestiji maksimuma çatdıran imza yeməkləri təqdim etmək istəyir.
Heç bir yemək imza yeməkləri siyahısında iki dəfə seçilə bilməz.
Heç bir reseptdə törəmə kimi göstərilməyən hər hansı bir yemək, dəyəri 0 və prestiji 0 olan elementar hesab edilir.
Yemək, nəticə olaraq reseptlər siyahısında bir neçə dəfə görünə bilər; bir yeməyi əldə etməyin bir neçə yolu varsa, bərabər ümumi xərclərlə ən aşağı ümumi dəyəri verən seçilir. Əgər ümumi xərclər eynidirsə, ən yüksək ümumi prestijə malik yemək seçilir.
Reseptlər elədir ki, D yeməyi, bir və ya bir neçə tərkib əlavə edərək D-dən əldə edilə bilməz.
Birinci sətir tam ədəd - büdcə B (0 ≤ B ≤ 10 000) ehtiva edir. İkinci sətir reseptlərin sayı n (0 ≤ n ≤ 10^6) ehtiva edir. Növbəti n sətirin hər biri, boşluqlarla ayrılmış aşağıdakı elementlər şəklində resepti təsvir edir: törəmə yeməyin adı (sətir); əsas yeməyin adı (sətir); əlavə edilən tərkib (sətir); əlavə edilən qiymət (tam ədəd); əlavə edilən prestij (tam ədəd).
10 000-dən çox fərqli yemək (elementar və ya törəmə) yoxdur;
Reseptlərdə qiymət və prestij 1-dən 10 000-ə qədər dəyişir (daxil olmaqla);
Sətirlər 20-dən çox olmayan ASCII simvolu (yalnız hərflər, rəqəmlər və _) ehtiva edir.
İki sətir çıxarın, hər biri bir tam ədəd ehtiva edir. Birinci sətirdə büdcə daxilində maksimum yığılmış prestiji çıxarın. İkinci sətirdə maksimum yığılmış prestijə uyğun minimum ümumi dəyəri çıxarın, mütləq büdcədən az və ya ona bərabər olmalıdır.
Nümunə 1