Pendir yemək#569

Pendir yemək

2 saniyə

64 meqabayt

Çətin

Flatland pendir fabrikində, pendiri çox sevən və mağaza üçün hazırlanmış pendir ehtiyatını tez-tez azaldan siçanlar yaşayır.

Fabrikdə $m$ siçan yaşayır. $i$ -ci siçan üçün onun pendir yemə sürəti $s_{i}$ s_i məlumdur, yəni bu siçan saatda $s_{i}$ s_i qram pendir yeyə bilər.

Son vaxtlar siçanlar fabrikin istehsal qrafiki haqqında məlumat əldə ediblər. $n$ ədəd pendir təkəri istehsal olunacaq. Hər təkər üçün aşağıdakı məlumatlar verilib: $r_{i}$ r_i — hazır olacağı saatın başlanğıcı, $d_{i}$ d_i — xarab olmağa başlayacağı saatın başlanğıcı, və $p_{i}$ p_i — təkərin çəkisi qramla.

Siçanlar bütün pendiri yeməyə qərar veriblər. İstənilən anda hər bir siçan hər hansı bir pendir təkərindən yeyə bilər. Siçanlar zərif canlılardır: eyni zamanda bir təkərdən yalnız bir siçan yeyə bilər. Lakin istənilən anda siçan bir təkəri yeməyi dayandırıb digərinə, hətta əvvəllər başqa siçanın yediyi bir təkərə keçə bilər.

Siçanlar pendirin xarab olmağa başlamasından sonra onu yeməyi sevmirlər, lakin heç bir pendiri yeyilməmiş qoya bilməzlər. Onlar pendirin yeyilməsi prosesini elə tənzimləmək istəyirlər ki, $t$ dəyəri — istənilən təkərin xarab olmağa başladıqdan sonra yeyilməyə davam etdiyi maksimum saat sayı — minimum olsun. Siçanlara pendiri bu şəkildə yeməkdə kömək edin.

Giriş

Birinci sətirdə iki tam ədəd $n$ və $m$ ( $1 \leq n, m \leq 30$ 1 \le n, m \le 30) verilir. Sonra $n$ sətir pendir təkərlərini təsvir edir: hər biri üç tam ədəd $p_{i}$ p_i, $r_{i}$ r_i, $d_{i}$ d_i ( $1 \leq p_{i} \leq 1 0^{5}$ 1 \le p_i \le 10^5, $0 \leq r_{i} < d_{i} \leq 1 0^{7}$ 0 \le r_i < d_i \le 10^7) ehtiva edir. Sonra $m$ sətir gəlir, hər biri bir tam ədəd $s_{j}$ s_j ( $1 \leq s_{j} \leq 1 0^{5}$ 1 \le s_j \le 10^5) göstərir.

Çıxış

Bir real ədəd çap edin — axtarılan minimum $t$ dəyəri. Cavabı ən azı $1 0^{- 4}$ 10^{-4} dəqiqliklə çap edin.

Nümunələr

Nümunə 1

Qeyd

Nümunənin izahı

Birinci nümunədə siçanlar pendiri aşağıdakı kimi yeməlidirlər. Əvvəlcə birinci siçan birinci təkəri yeməyə başlayır. İkinci təkər hazır olan kimi, o, birincini buraxıb ikinciyə keçir (bu zaman birinci təkərdə $9$ qram qalır). İkinci siçan birinci təkəri yeyir. $2.5$ saatdan sonra birinci siçan ikinci təkəri bitirir (xarab olmağa başladıqdan $0.5$ saat sonra) və yenidən birincini yeməyə qayıdır; bu vaxta ikinci siçan birinci təkərdən daha $5$ qram yeyib və $4$ qram qalır. Beləliklə, daha bir saat sonra birinci siçan birinci təkəri bitirir, yenə də xarab olmağa başladıqdan $0.5$ saat sonra.

İkinci nümunədə siçan pendiri xarab olmağa başlamazdan əvvəl bitirməyə çatdırır.