Sürət məhdudiyyətinin dəyəri

3031-ci ilə qədər ICPC o qədər populyarlaşdı ki, dünya finalındakı bütün komandaları yerləşdirmək üçün tamamilə yeni bir şəhər inşa etmək lazım gəldi. Şəhər gözəl dizayn edilmiş və yol şəbəkəsi ilə təchiz olunmuşdur. Təəssüf ki, büdcə planlaşdırılarkən şəhərsalma mütəxəssisləri sürət məhdudiyyəti nişanlarının dəyərini nəzərə almadılar. Onlar sizdən lazım olan minimum əlavə vəsaiti müəyyən etməyə kömək etməyinizi xahiş etdilər.

ICPC-nin yol şəbəkəsi hər biri iki kəsişmə nöqtəsini birləşdirən yollardan ibarətdir. Hər bir yol ikitərəfli və hər iki istiqamət üçün eyni sürət məhdudiyyəti ilə təchiz edilmişdir. İqtisadiyyat məqsədilə mümkün olan minimum sayda yollar istifadə edilmişdir. Başqa sözlə, hər hansı bir kəsişmə nöqtəsindən digərinə yalnız bir marşrut mövcuddur.

Sürət məhdudiyyəti nişanları hər hansı bir sürücünün hər hansı bir marşrut üzrə sürət məhdudiyyətinin dəyişə biləcəyi bütün yerlərdə quraşdırılmalıdır. Dəqiq desək, əgər hər hansı bir kəsişmə nöqtəsində ən azı iki fərqli sürət məhdudiyyəti olan yollar kəsişirsə, o zaman bu kəsişmə nöqtəsindən çıxan bütün yollarda sürət məhdudiyyəti nişanı quraşdırılmalıdır. Qeyd edək ki, bəzi yollarda hər iki ucunda bir nişan olmaqla iki sürət məhdudiyyəti nişanı tələb oluna bilər.

Bir sürət məhdudiyyəti nişanının quraşdırılması $c$ dollar başa gəlir. Həmçinin, hər hansı bir yolda sürət məhdudiyyətini artırmaqla təhlükəsizliyi və keyfiyyəti artırmaq mümkündür ki, bu da tələb olunan sürət məhdudiyyəti nişanlarının sayını azalda bilər. Bir yolda sürət məhdudiyyətini $x$ km/saat artırmaq (hər iki istiqamətdə) $x$ dollar başa gəlir. Şikayətlərin qarşısını almaq üçün şəhər şurası artıq təyin edilmiş sürət məhdudiyyətlərini azaltmağa icazə vermir.

Şəkil B.1 həm giriş məlumatları 1, həm də giriş məlumatları 2 üçün vəziyyəti təsvir edir.