Avtobus
Vasili avtobus sürücüsü olaraq işləyir və onun işi olduqca çətindir: o, sərnişinləri A nöqtəsindən B nöqtəsinə daşıyır. Bu işi təhlükəsiz və mümkün qədər tez yerinə yetirməlidir. Bundan əlavə, hər bir sürücü yol qaydalarına və normalara riayət etməlidir, əks halda yerli polis tərəfindən cərimələnə bilər.
Vasilinin marşrutu N (1 ≤ N ≤ 1000) ardıcıl keçdiyi seqmentlərdən ibarətdir, 1-ci seqmentdən başlayaraq N-ci seqmentdə bitir. Hər bir seqmentin uzunluğu kilometr ilə D_{i} (1 ≤ D_i ≤ 1000) olaraq verilmişdir.
Vasilinin marşrutunda sürət məhdudiyyətləri mövcuddur. Hər bir seqmentin öz sürət məhdudiyyəti L_i km/saat (1 ≤ L_i ≤ 100000) var. Əgər sürücü i-ci seqmentdə sürət həddini aşarsa, avtobus sürücüsü dərhal polis tərəfindən saxlanılacaq və müvafiq sənədlərin doldurulmasına H_i (1 ≤ H_i ≤ 1000) saat sərf olunacaq. Sürücü hər seqmentdə bir dəfədən çox saxlanıla bilməz.
Avtobus marşrut boyunca Vasili tərəfindən marşrutun əvvəlində (A nöqtəsində) seçilən sabit sürətlə S gedir. Avtobusun maksimal konstruktiv sürətini aşmaq olmaz, bu isə M km/saat (1 ≤ M ≤ 100000) ilə müəyyən edilir.
Zəhmət olmasa, Vasiliyə son nöqtə B-yə mümkün qədər tez çatmaq üçün düzgün sürəti seçməkdə kömək edin.
Giriş verilənləri
Giriş məlumatlarının ilk sətiri test hallarının sayını T ehtiva edir. Sonra T test halları təsviri gəlir, T ≤ 100.
Hər bir test halı əvvəlcə ayrı bir sətirdə boşluqla ayrılmış 2 ədəd ehtiva edir: Vasilinin marşrutundakı seqmentlərin sayı N və avtobusun maksimal icazə verilən sürəti M. Sonrakı hər bir i-ci sətir hər bir N seqmentinin təsvirini ehtiva edir və müvafiq i-ci seqment üçün boşluqla ayrılmış D_i, L_i və H_i dəyərlərini ehtiva edir.
Çıxış verilənləri
Hər bir test halı üçün avtobusun optimal sürətini çıxarın. Əgər cavab qeyri-müəyyəndirsə, ən böyük dəyəri seçin.