Pendir yemək
Flatlandiya pendir zavodunda siçanlar yaşayır. Onlar pendiri çox sevirlər və tez-tez mağazaya göndərilmək üçün hazırlanmış pendir ehtiyatlarını məhv edirlər.
Zavodda ümumilikdə m siçan yaşayır. i-ci siçanın pendir yemə sürəti s_i məlumdur, yəni siçan saatda s_i qram pendir yeyə bilər.
Son zamanlar siçanlar zavodun yaxın gələcək üçün iş planını öyrəniblər. Zavod n baş pendir istehsal etməyi planlaşdırır. Hər bir baş pendir haqqında məlumatlar belədir: r_i - hansı saatın əvvəlində istehsal olunacağı, d_i - hansı saatın əvvəlində xarab olmağa başlayacağı və p_i - pendirin qramla çəkisi.
Siçanlar bütün pendiri yeməyə qərar veriblər. Hər an hər bir siçan müəyyən bir baş pendir yeyə bilər. Siçanlar təmizkardırlar və eyni baş pendiri eyni anda bir neçə siçan yeyə bilməz. Bununla belə, hər an siçan baş pendiri yeməyi dayandırıb başqa birinə, o cümlədən əvvəllər başqa bir siçanın yediyi baş pendirə keçə bilər.
Siçanlar pendir xarab olmağa başladıqdan sonra yeməyi sevmirlər. Amma pendiri yarımçıq qoymaq olmaz. Onlar pendiri elə yeməyi təşkil etməyə qərar veriblər ki, t böyüklüyü, yəni hansısa baş pendiri xarab olmağa başladıqdan t saat sonra hələ də yeməyə davam edirlər, minimal olsun. Siçanlara bunu necə edəcəyini öyrənməyə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətiri iki tam ədəd n və m (1 <= n, m <= 30) ehtiva edir. Növbəti n sətir hər biri üç tam ədəd: p_i, r_i və d_i (1 <= p_i <= 10^5, 0 <= r_i < d_i <= 10^7) ehtiva edir. Daha sonra m sətir gəlir, hər biri bir tam ədəd s_j (1 <= s_j <= 10^5) ehtiva edir.
Çıxış verilənləri
Bir real ədəd çıxarın - axtarılan minimal t. Cavabı 10^{-4} dəqiqliklə çıxarın.
Nümunəyə izah
Birinci nümunədə siçanlar pendiri belə yeməyi təşkil etməlidirlər. Əvvəlcə birinci siçan birinci baş pendiri yeməyə başlayır. İkinci baş pendir ortaya çıxanda, o, birinci baş pendiri yeməyi dayandırır və ikinci baş pendiri yeməyə başlayır (bu anda birincidən 9 qram qalıb). İkinci siçan birinci baş pendiri yeməyə başlayır. 2.5 saat sonra birinci siçan ikinci baş pendiri yeyib bitirir (o, xarab olmağa başladıqdan 0.5 saat sonra) və yenidən birinci baş pendiri yeməyə başlayır (bu müddət ərzində ikinci siçan birinci baş pendirdən daha 5 qram yeyib və ondan 4 qram qalıb). Beləliklə, bir saat ərzində birinci siçan birinci baş pendiri yeyib bitirir, həmçinin xarab olmağa başladıqdan 0.5 saat sonra.
İkinci nümunədə siçan pendiri xarab olmadan yeyib bitirə bilir.