Vaxtlama
Qalaktikaların toqquşması yaxınlaşır!
Gizli MdI tərəfindən idarə olunan bir qalaktika, süd yolumuzu ilhaq etməyə çalışır, lakin qalaktik hökumət vəziyyəti dəyişdirmək üçün planlar hazırlayıb.
Kəşfiyyat agentliyimiz düşmənin qərargahına sızıb və təəccüblü məlumatlar əldə edib. Düşmən öz bölmələrini hər bir qalada müəyyən bir sxemə uyğun olaraq hərəkət etdirir: hər bir qala üçün hər zaman vahidində (uçuş vaxtı nəzərə alınmır) bölmələrin bir hissəsi digər qalalara köçürülür.
Hökumət indi hücum üçün bir vaxt təyin edib. Sizin vəzifəniz zəif nöqtələri hesablamaqdır. Lakin düşmənin qalaktikası çox uzaqda olduğu üçün ora uçmaq bir zaman vahidi çəkir. Bundan əlavə, MdI-nin hədəfimizi tanıyacağına və dərhal hücum nöqtəmizə çata bilən bütün gəmiləri (bir əlaqə vasitəsilə, istiqamətindən asılı olmayaraq) işə salacağına əminik. Casus sizə bu güclərin yalnız statistik dəyərlər olduğunu, yəni bir növ göstərici kimi olduğunu bildirdi.
Giriş verilənləri
Girişin ilk sətri test hallarının sayını (1 ≤ T ≤ 10) ehtiva edir. Hər bir test halı düşmən qalalarının sayını N (1 ≤ N ≤ 100), əlaqələrin sayını l (0 ≤ l ≤ (N-1)^2) və hücum edəcəyimiz zamandan indiyə qədər olan vaxtı t (0 ≤ t ≤ 5000) bildirən üç tam ədəd ilə başlayan bir sətirdən ibarətdir. İkinci sətir hər bir qalada yerləşdirilmiş qoşunların gücünü göstərən N ədəd u_i (0 ≤ u_i ≤ 1000) ikiqat rəqəmlərini ehtiva edir, ardınca l sətir əlaqələri ehtiva edir. Hər bir əlaqə iki tam ədəd s_j (0 ≤ s_j < N), t_j (0 ≤ t_j < N) ilə təsvir edilir, əlaqənin mənbəyi və hədəfini və hər zaman vahidində s_j-dən t_j-yə köçürülən bölmələrin hissəsini göstərən bir ikiqat p_j (0 < p_j ≤ 1) ilə təsvir edilir.
Çıxış verilənləri
Düşmən qalaktikasının ən aşağı göstəricisini 10^{-6}-dan az olan mütləq və ya nisbi səhvlə çap edin.
Şəkil 1 – İlk nümunənin statistik gücləri ilk zaman addımından əvvəl və sonra.
Şəkil 2 – Hər bir qalada qarşılaşılacaq qüvvələrin gücü. Qeyd edək ki, əlaqələr hər iki istiqamətdə istifadə olunur.