На сырном заводе во Флатландии живут мыши. Они очень любят сыр и часто уничтожают запасы сыра, приготовленные для отправки в магазин.
Всего на заводе живет \(m\) мышей. Для \(i\)-й мыши известна ее скорость поедания сыра \(s_i\), мышь может съесть \(s_i\) грамм сыра в час.
Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить \(n\) головок сыра. Про каждую головку известны \(r_i\) к началу какого часа она будет изготовлена, \(d_i\) в начале какого часа она начнет портиться, и \(p_i\) вес головки сыра в граммах.
Мыши решили съесть весь сыр. В любой момент времени каждая мышь может есть некоторую головку сыра. Мыши существа брезгливые, и одну и ту же головку сыра не могут есть одновременно несколько мышей. При этом в любой момент времени мышь может решить прекратить есть головку сыра и приняться за другую, в том числе ту, которую ранее ела другая мышь.
Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина \(t\), такая что какую-либо головку все еще продолжают есть через \(t\) часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 30\), \(1 \le m \le 30\)). Следующие \(n\) строк содержит по три целых числа: \(p_i\), \(r_i\) и \(d_i\) (\(1 \le p_i \le 10^5\), \(0 \le r_i \lt d_i \le 10^7\)). Далее следуют \(m\) строк, каждая из которых содержит по одному целому числу \(s_j\) (\(1 \le s_j \le 10^5\)).
Выведите одно вещественное число — искомое минимальное \(t\). Ваш ответ должен отличаться от правильного не больше чем на \(10^{-4}\).
Комментарий к примеру тестов
В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2.5 часа первая мышь доедает вторую головку сыра (на 0.5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0.5 часа позже чем она начала портиться.
Во втором примере мышь успевает съесть сыр до того как он начинает портиться
2 2 13 0 4 10 1 3 4 2
0.5
1 1 1 0 1 1
0.0
Недавно разведка Флатландии перехватила секретный документ. Сотрудники первого отдела разведки подозревают, что это список пар городов, между которыми в соседней Берляндии проложены автомагистрали. Попытавшись сопоставить номера городов с городами Берляндии, сотрудники убедились что это можно сделать.
Однако сотрудники второго отдела высказали другое предположение. Они предположили, что этот список — это в точности список пар городов, между которыми в Берляндии нет автомагистрали. Попытавшись сопоставить номера городов с городами в Берляндии, они также убедились, что это можно сделать.
Директор разведки в затруднении. Решив проверить, возможно ли такое, он дал задание сотрудникам третьего отдела. Директор попросил их выяснить, может ли так быть, что между некоторыми городами в Берляндии проложены автомагистрали, а между некоторыми — нет, и существует самодвойственный список пар. Список пар целых чисел от 1 до \(n\) называется самодвойственным, если можно занумеровать города так, чтобы он задавал все пары городов, между которыми есть автомагистраль, а можно перенумеровать города таким образом, чтобы тот же самый список задавал все пары городов, между которыми автомагистрали нет.
Помогите сотрудникам третьего отдела решить поставленную задачу.
Входной файл содержит одно число \(n\) — количество городов в Берляндии (\(1 \le n \le 100\)).
Если ответа на задачу не существует, выведите в первой строке выходного файла слово «NO».
В противном случае в первой строке выходного файла слово «YES». На второй строке выведите \(m\) — количество автомагистралей в Берляндии. Занумеруем города некоторым образом от 1 до n.
Далее выведите \(m\) строк по два числа — пары городов, между которыми есть автомагистрали.
Между парой городов должно быть не более одной автомагистрали, автомагистраль не должна соединять город сам с собой.
На следующей строке выведите \(n\) целых чисел, для города \(i\) выведите число \(a_i\), такое, что если в приведенном выше списке из \(m\) пар заменить все числа \(i\) на \(a_i\), то получится в точности список всех пар городов, между которыми нет автомагистрали. Все \(a_i\) должны быть различны.
2
NO
4
YES 3 1 2 2 3 3 4 3 1 4 2
В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.
Шоу состоит из \(n\) небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление \(i\) начинается через \(s_i\) минут от начала шоу и продолжается \(t_i\) минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).
Публика любит и представления со львами, и представления с тиграми. Дрессировщики просят вас помочь им распределить представления между львами и тиграми так, чтобы минимум из числа представлений с львами и числа представлений с тиграми был как можно больше.
Первая строка входного файла содержит число \(n\) (\(1 \le n \le 200\)). Следующие \(n\) строк содержат пары чисел \(s_i\), \(t_i\). (\(0 \le s_i \le 10^9\), \(1 \le t_i \le 10^9\))
Выведите в выходной файл \(n\) чисел. Число номер \(i\) должно быть равно \(1\), если в \(i\)-ом представлении участвуют львы, или \(2\), если участвуют тигры, или \(0\), если не участвуют ни те ни другие.
5 8 3 0 7 4 5 1 2 11 3 0 7 1 3 4 9 8 11 11 14
2 1 0 1 2