Bayrama Hazırlıq#4063
Bayram hazırlıqları bir çox işlərlə müşayiət olunur: nə geyinmək, kimi dəvət etmək, qonaqlara hansı menyunu təklif etmək və s. Bu işlərdən biri də məhsul alışıdır - masanı zənginləşdirmək istəyirik, amma mümkün qədər az maliyyə vəsaiti sərf edərək.
Təsəvvür edək ki, seçilmiş menyunu təmin etmək üçün P növ məhsul almaq lazımdır. Məhsullar M mağazada alına bilər və İnternet vasitəsilə hansı mağazalarda və hansı qiymətə məhsulların mövcud olduğu məlumdur.
Bütün mağazalar arasında, həmçinin ev ilə hər bir mağaza arasında məlum uzunluqda "birbaşa" yollar var (yol "birbaşa" hesab olunur, əgər bir nöqtədən digərinə hərəkət edərkən üçüncü məlum nöqtədən: evdən və ya mağazadan keçid baş vermirsə). Gəlin hesab edək ki, bütün yollar ikitərəfli hərəkətlidir.
Məlum olanlara əsasən:
məhsul sayına;
hər bir məhsulun alış həcminə;
mağaza sayına;
mağazalarda məhsulların mövcudluğu və qiymətinə;
marşrut nöqtələri arasında "birbaşa" yolların uzunluqlarına;
məsafə vahidi üçün yanacaq xərclərinin qiymətinə,
məhsul alışına sərf olunacaq minimum pul məbləğini müəyyən etmək tələb olunur (xərclər məhsullara sərf olunan pulun və mağazalara səyahət üçün sərf olunan yanacaq xərclərinin cəmindən ibarətdir). Səyahət evdən başlayıb evdə bitməlidir.
Birinci sətir boşluqla ayrılmış iki tam ədəd P və M ehtiva edir - müvafiq olaraq məhsul və mağaza sayı (1 ≤ P ≤ 5, 1 ≤ M ≤ 15).
İkinci sətir boşluqlarla ayrılmış P tam ədəd ehtiva edir - hər bir məhsulun alış həcmi (1 ≤Pi ≤ 100, 1 ≤ i ≤ P).
Növbəti M sətir hər biri boşluqlarla ayrılmış P tam ədəd ehtiva edir - mağazalarda məhsulların qiymətləri (0 ≤ Сji≤ 100, 1 ≤ i ≤ P, 1 ≤ j ≤ M). Qiymət 0 dəyəri məhsulun mağazada olmadığını göstərir. Hər bir məhsulun ən azı bir mağazada alınabiləcəyi təmin edilir. Hər bir mağazada ən azı bir məhsulun satıldığı təmin edilir.
Növbəti sətir boşluqlarla ayrılmış M tam ədəd ehtiva edir - evdən j-ci mağazaya "birbaşa" yolların məsafəsi (1 ≤ Lj ≤ 100, 1 ≤ j ≤ M).
Növbəti M-1 sətir (k-cı sətir) hər biri (M-k) tam ədəd ehtiva edir, boşluqlarla ayrılmış - k-cı mağaza ilə nömrəsi k-dan böyük olan bütün mağazalar (n mağazalar) arasında "birbaşa" yolun məsafəsi (1 ≤ Skn ≤ 100).
Sonuncu sətir bir tam ədəd T ehtiva edir - məsafə vahidi üçün yanacaq xərclərinin qiyməti (1 ≤ T ≤100).
Çıxış faylı bir tam ədəd ehtiva etməlidir - məhsul alışına sərf olunacaq minimum pul məbləği, yanacaq xərcləri nəzərə alınmaqla.
Nümunə (şəkilə baxın): qalın şəkildə hərəkət yolu, çərçivə ilə alış yerləri göstərilmişdir.
Nümunə 1