Поїдання сиру#569

Поїдання сиру

2 секунди

64 мегабайти

Складна

На сирному заводі у Флетлендії мешкають миші, які обожнюють сир і часто з'їдають запаси сиру, підготовлені до відправки в магазин.

На заводі живе $m$ мишей. Для $i$ -ї миші відома її швидкість поїдання сиру $s_{i}$ s_i, тобто вона може з'їдати $s_{i}$ s_i грамів сиру за годину.

Нещодавно миші дізналися розклад виробництва на фабриці. Планується виготовити $n$ сирних голів. Для кожної голови відомо: $r_{i}$ r_i — початок години, коли вона буде готова, $d_{i}$ d_i — початок години, коли вона почне псуватися, та $p_{i}$ p_i — вага голови у грамах.

Миші вирішили з'їсти весь сир. У будь-який момент кожна миша може їсти якусь одну сирну голову. Миші — вибагливі створіння: одночасно одну й ту ж голову може їсти не більше однієї миші. Проте будь-якої миті миша може припинити їсти одну голову і почати їсти іншу, навіть ту, яку до цього їла інша миша.

Миші не люблять їсти сир після того, як він почав псуватися, але залишати його недоїденим не можуть. Вони хочуть організувати поїдання так, щоб значення $t$ — максимальна кількість годин, протягом яких будь-яка голова ще доїдається після початку псування, — було мінімальним. Допоможіть мишам так організувати поїдання сиру.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $m$ ( $1 \leq n, m \leq 30$ 1 \le n, m \le 30). Наступні $n$ рядків описують сирні голови: у кожному рядку три цілі числа $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). Далі йдуть $m$ рядків — у кожному з яких записано по одному цілому числу $s_{j}$ s_j ( $1 \leq s_{j} \leq 1 0^{5}$ 1 \le s_j \le 10^5).

Вихідні дані

Виведіть одне дійсне число — шуканий мінімум $t$ . Відповідь повинна бути виведена з точністю принаймні $1 0^{- 4}$ 10^{-4}.

Приклади

Приклад 1

Примітка

Пояснення до прикладу

У першому прикладі миші можуть організувати поїдання так. Спочатку перша миша починає їсти першу голову. Коли з'являється друга голова, вона перестає їсти першу і переключається на другу (на цей момент на першій голові залишається $9$ грам). Тоді другу мишу переводять до поїдання першої голови. Через $2.5$ години перша миша доїдає другу голову ( $0.5$ години після початку псування) і повертається до першої; на цей момент друга миша встигає з'їсти ще $5$ грамів першої голови, і залишається $4$ грами. Ще через годину перша миша доїдає першу голову, також $0.5$ години після початку псування.

У другому прикладі миша встигає доїсти сир до початку псування.