Südün nasosu
Fermer Con, süd imperiyasını genişləndirmək məqsədilə yeni bir ferma alıb. Bu ferma qonşu şəhərə boru şəbəkəsi vasitəsilə bağlıdır və FC, südü fermadan şəhərə vurmaq üçün ən yaxşı boru dəstini seçmək istəyir.
Boru şəbəkəsi n birləşmə nöqtəsi (boruların son nöqtələri) ilə təsvir olunur və bu nöqtələr 1-dən n-ə qədər nömrələnib. Birləşmə nöqtəsi 1 FC-nin fermasını, birləşmə nöqtəsi n isə şəhəri təmsil edir. Şəbəkədə m ikitərəfli boru mövcuddur və hər biri iki birləşmə nöqtəsini birləşdirir. i-ci borunun qiyməti c[i] dollar və onun dəstəklədiyi axın sürəti saniyədə f[i] litrdir.
FC, birləşmə nöqtələri 1 və n arasında bir yol üçün borular almaq istəyir. Yolun ümumi dəyəri, yol boyunca istifadə olunan boruların qiymətlərinin cəmidir. Yol boyunca axın sürəti isə həmin yoldakı boruların ötürmə qabiliyyətlərinin minimumu ilə müəyyən edilir (çünki bu, yoldakı axın üçün dar boğaz rolunu oynayır). FC, axın qabiliyyətini yolun dəyərinə bölərək bu nisbəti maksimumlaşdırmaq istəyir. 1-dən n-ə qədər belə bir yolun mövcud olduğu təmin edilir.
Giriş Məlumatları
Birinci sətir n (2 ≤ n ≤ 1000) və m (1 ≤ m ≤ 1000) ədədlərini ehtiva edir. Sonrakı m sətirin hər biri dörd tam ədəd şəklində bir borunu təsvir edir: a və b (boru ilə birləşdirilən iki fərqli birləşmə nöqtəsi), c (qiymət) və e (ötürmə qabiliyyəti). Qiymət və ötürmə qabiliyyəti 1-dən 1000-ə qədər olan təbii ədədlərdir.
Çıxış Məlumatları
Optimal cavabı 10^6 ilə vurulmuş şəkildə, tam ədədə qədər kəsilmiş (yəni, əgər bu ədəd özü tam ədəd deyilsə, ən yaxın aşağı tam ədədə yuvarlanmış) çıxarın.
Nümunə
Nümunədə yalnız bir yol 1-dən n-ə qədər mövcuddur. Onun ötürmə qabiliyyəti min(3, 4) = 3, və dəyəri 2 + 5 = 7.