Поїдання сиру
На сирному заводі у Флатландії живуть миші, які обожнюють сир і часто знищують запаси, призначені для відправки в магазин.
На заводі мешкає m мишей. Для кожної i-ї миші відома її швидкість поїдання сиру s_i, тобто вона може з'їсти s_i грамів сиру за годину.
Нещодавно мишам став відомий план роботи заводу на найближчий час. Планується виготовити n головок сиру. Для кожної головки відомо: r_i - до якої години вона буде виготовлена, d_i - з якої години вона почне псуватися, і p_i - вага головки сиру в грамах.
Миші вирішили з'їсти весь сир. У будь-який момент часу кожна миша може їсти певну головку сиру. Миші - істоти бридливі, тому одну й ту ж головку сиру не можуть їсти одночасно кілька мишей. Проте, в будь-який момент часу миша може припинити їсти одну головку сиру і перейти до іншої, навіть якщо її раніше їла інша миша.
Миші не люблять їсти сир після того, як він почав псуватися. Але залишати сир недоїденим вони не можуть. Вони вирішили організувати поїдання сиру так, щоб величина t, яка означає, що якусь головку все ще продовжують їсти через t годин після того, як вона почала псуватися, була мінімальною. Допоможіть мишам з'ясувати, як це зробити.
Вхідні дані
Перший рядок вхідного файлу містить два цілі числа n і m (1 <= n, m <= 30). Наступні n рядків містять по три цілі числа: p_i, r_i і d_i (1 <= p_i <= 10^5, 0 <= r_i < d_i <= 10^7). Далі йдуть m рядків, кожен з яких містить одне ціле число s_j (1 <= s_j <= 10^5).
Вихідні дані
Виведіть одне дійсне число - шукане мінімальне t. Відповідь виведіть з точністю 10^{-4}.
Пояснення до прикладу
У першому прикладі миші повинні організувати поїдання сиру наступним чином. Спочатку перша миша починає їсти першу головку сиру. Коли з'являється друга головка, вона перестає їсти першу і починає їсти другу (в цей момент від першої залишилося 9 грамів). Друга миша береться їсти першу головку сиру. Через 2.5 години перша миша доїдає другу головку сиру (на 0.5 години пізніше, ніж вона почала псуватися) і знову починає їсти першу (друга миша за цей час з'їла ще 5 грамів від першої головки і від неї залишилося 4 грами). Таким чином, ще за годину перша миша доїдає першу головку, також на 0.5 години пізніше, ніж вона почала псуватися.
У другому прикладі миша встигає з'їсти сир до того, як він починає псуватися.