Mineral su haqqında tapşırıq

Hər kəsə məlumdur ki, ACM 2004 proqramlaşdırma çempionatının finalı Praqada keçirilib. Məşhur memarlığı və mədəniyyəti ilə yanaşı, Praha həm də dünyada mineral suyu ilə tanınır. Mineral suyun həddindən artıq istehlakı iştirakçıların sağlamlığı üçün zərərli ola bilsə də, bir çox komandalar münasib qiymətə əla mineral sudan istifadə fürsətini qaçırmadılar.

Yeni bir mineral su şirkəti olan Drink Everywhere məhsullarını $n$ Avropa şəhərinə çatdırmağı planlaşdırır. Artezyan quyusu Praqanın yaxınlığında yerləşir, bunu şəhər nömrəsi $1$ kimi götürəcəyik. Digər şəhərlərə mineral su çatdırmaq üçün şirkət Carry Everywhere adlı logistika şirkətinin xidmətlərindən istifadə etməyi planlaşdırır; bu şirkət $m$ nəqliyyat marşrutu təklif edir. Hər bir marşrut onu birləşdirən şəhərləri (yük iki istiqamətdə daşına bilər), marşrutun tutumunu — yəni həmin marşrutla gündə neçə litr mineral su daşına biləcəyini və bir litr mineral suyun daşınma xərci­ni müəyyən edir. Bəzi hallarda daha sərfəli və ya zəruri olaraq bir neçə marşrutu ard-arda istifadə etmək, hətta mineral suyu bir şəhərə çatdırmaq üçün bir neçə fərqli yolla daşınmasını təmin etmək lazım gələ bilər.

Hər bir şəhər yerli restoranlar və pub'lar tərəfindən bir litr mineral suya ödənilən qiymətlə xarakterizə olunur. Qəbul edə bilərsiniz ki, hər bir şəhərdə mineral suya tələbat kifayət qədər yüksəkdir, məhsul həmişə müştəri tapacaq.

Drink Everywhere Praqada birbaşa mineral su satmaq fikrində deyil, çünki burada rəqabət çox güclüdür, ona görə də şirkət hələlik mineral suyu yalnız digər şəhərlərdə satmağı planlaşdırır. Onlara bir gündə əldə edə biləcəkləri maksimal gəliri hesablamaqda kömək edin.