Biletsiz səyahət
Vircili Milli Təhlükəsizlik Agentliyinin sadiq əməkdaşıdır. Hər gün işə gedərkən qatarla uzun müddət yol qət edir və bu müddətdə öz həyatını və vəziyyətini düşünmək imkanı tapır. Riyaziyyatçı olaraq, o, hərçənd ki, səfərləri üçün mütləq şəkildə ödəniş edir, bilet yoxlayanların nadir hallarda onun biletini yoxladığını müşahidə edir. İllərlə təcrübəsi olan Vircili, hər bir şəhər cütlüyü arasında yoxlanılma ehtimalı haqqında kifayət qədər yaxşı təsəvvürə malikdir.
Bəlkə o, ödənişdən qaça bilər? Əlbəttə, əgər onu biletsiz qatarla tutarlarsa, biletin qiymətindən xeyli çox olan cərimə ödəməli olacaq. Amma yenə də... Bəlkə (səfərin bir hissəsi üçün) ödəniş etməmək və tutulanda cərimə ödəmək daha ucuzdur?
Şəhərdən A şəhərə B biletin qiyməti müəyyən başlanğıc dəyəri s və A ilə B arasında ən qısa yol üzrə hər kilometr üçün müəyyən kiçik məbləğ p təşkil edir (bilet yalnız ən qısa yola etibarlıdır). Əgər biletsiz tutulursunuzsa, sonuncu şəhərdən başlayaraq qatarın keçdiyi dəmir yolu hissəsi üzrə hər kilometr üçün müəyyən sabit y və məbləğ p ödəməlisiniz. Qaydalar deyir ki, biletsiz tutulduğunuzda növbəti dayanacaqda düşməlisiniz. Lakin belə gizli agentliyin əməkdaşı olan Vircili maskalanma ustasıdır: bilet yoxlayanlar onu heç vaxt tanımayacaq və o, sanki tutulmamış kimi səfərini davam etdirə bilər.
Virciliyə təcrübəsinə əsaslanaraq yol tapmaq və gündəlik gözlənilən xərclərini minimallaşdırmaq üçün hansı biletləri almalı olduğunu göstərən bir kompüter proqramı yazmağa kömək edin.
Üçüncü nümunənin vizualizasiyasını nəzərdən keçirək. 1 şəhərindən 4 şəhərinə çatmaq üçün ən yaxşı variant 1 şəhərindən 2 şəhərinə qədər 20 (10 + 1 × 10) qiymətində bilet almaq, sonra 2 şəhərindən 3 şəhərinə qədər 22 (0.1 × (100 + 1 × 120)) gözlənilən qiymətlə biletsiz getmək və nəhayət 3 şəhərindən 4 şəhərinə qədər 20 (10 + 1 × 10) qiymətində bilet almaqdır. Səfərin ümumi qiyməti 62 (20 + 22 + 20) olacaq ki, bu da verilmiş dəmir yolu şəbəkəsi üçün ən yaxşısıdır.
________________________________
^1 Gündəlik gözlənilən səfər xərci E[C] = P_kC_k ilə ifadə olunur, burada P_k səfər xərci C_k olan ehtimaldır, cəmi bütün mümkün xərclər üzrə götürülür. Gözlənilən dəyərlər əlavə olunur, yəni E[X+Y] = E[X] + E[Y].
Giriş verilənləri
Birinci sətir testlərin sayını göstərir, ən çox 100. Hər bir test aşağıdakılardan ibarətdir:
yeddi tam ədəddən ibarət bir sətir:
n (2 ≤ n ≤ 200): dəmir yolu şəbəkəsindəki şəhərlərin sayı;
m (1 ≤ m ≤ n(n-1)/2)): dəmir yolu şəbəkəsindəki birbaşa əlaqələrin sayı;
start (1 ≤ start ≤ n): Vircilinin yaşadığı şəhərin nömrəsi;
end (1 ≤ end ≤ n, start ≠ end): Vircilinin işlədiyi şəhərin nömrəsi;
s (1 ≤ s ≤ 1000): biletin başlanğıc qiyməti;
p (1 ≤ p ≤ 1000): bilet və ya cərimə üçün kilometr başına qiymət;
y (s < y ≤ 1000): cərimənin sabit hissəsi.
m sətir, şəhərlər arasında iki tərəfli yolları təyin edən dörd tam ədəd. i-ci sətir aşağıdakıları ehtiva edir:
a_i (1 ≤ a_i ≤ n): i hissəsinin bir tərəfindəki şəhərin indeksi;
b_i (a_i < b_i ≤ n): i hissəsinin digər tərəfindəki şəhərin indeksi;
c_i (0 ≤ c_i ≤ 100): i hissəsində bilet yoxlayanların biletinizi yoxlama ehtimalı, faizlə ifadə olunur;
d_i (1 ≤ d_i ≤ 1000): a_i və b_i şəhərləri arasında i hissəsinin uzunluğu, kilometr ilə;
Hər hansı (a_i, b_i) və (a_j, b_j) cütü üçün, burada i ≠ j, (a_i, b_i) ≠ (a_j, b_j).
Çıxış verilənləri
Hər bir test üçün başlanğıc və son şəhər arasında gözlənilən səfər xərclərini iki onluq dəqiqliklə ayrıca sətirdə yazın.