Ханбёль перед выпуском хочет пожертвовать несколько полупроводников собственного изготовления для объединения студенческих клубов по программированию. Чтобы создать как можно больше полупроводников, он хочет минимизировать стоимость производства одного полупроводника.
Полупроводник представляет собой ориентированный граф с $N$ вершинами и $M$ ребрами. Каждая вершина пронумерована от $1$ до $N$, и каждая вершина $i$ имеет потенциальную энергию $E_i$. Потенциальная энергия является вещественным числом, при этом $E_1 = 1.0$ и $E_N = -1.0$ зафиксированы, а потенциальные энергии остальных вершин Ханбёль может выбрать произвольно. Кроме того, вершины $1$ и $N$ являются особыми: в вершину $1$ не входят никакие ребра, а из вершины $N$ не выходят никакие ребра.
Каждое ребро $e = (u, v)$, составляющее полупроводник, может передавать положительную и отрицательную энергию из вершины $u$ в вершину $v$. Каждое ребро имеет значение, называемое эффективностью передачи энергии. Если Ханбёль передает положительную энергию $p_e (\ge 0)$ и отрицательную энергию $m_e (\le 0)$ через ребро с эффективностью передачи положительной энергии $a_e (\ge 0)$ и эффективностью передачи отрицательной энергии $b_e (\ge 0)$, то количество энергии, передаваемое ребром, составляет $(a_e p_e + b_e m_e)$. Однако, если энергия, передаваемая через ребро $e = (u, v)$, не удовлетворяет условию $p_{(u,v)} + m_{(u,v)} \ge E_u - E_v$, полупроводник может выйти из строя из-за перегрузки.
Стоимость производства полупроводника равна сумме энергий, передаваемых каждым ребром, составляющим полупроводник. Помогите Ханбёлю, который хочет совершить доброе дело, подобрать потенциальную энергию каждой вершины и количество энергии, передаваемое по каждому ребру, так, чтобы полупроводник не вышел из строя, а стоимость производства была минимальной.
Входные данные
В первой строке заданы количество вершин $N$ и количество ребер $M$, разделенные пробелом ($3 \le N \le 500$; $1 \le M \le N(N - 1)$).
Начиная со второй строки, заданы $M$ строк, содержащих информацию о ребрах. Каждая строка содержит 4 целых числа $u, v, a, b$, разделенных пробелом. Это означает, что существует ребро из вершины $u$ в вершину $v$ с эффективностью передачи положительной энергии $a$ и эффективностью передачи отрицательной энергии $b$. Входные данные не содержат кратных ребер. ($1 \le u, v \le N; u \neq v; 0 \le a, b \le 10^9$)
Выходные данные
Выведите минимальную стоимость производства одного полупроводника. Если стоимость производства может стать меньше $-3 \times 10^{-9}$, выведите слово HAPPY, выражающее настроение Ханбёля, который может получать деньги каждый раз при производстве полупроводника. Допускается абсолютная/относительная погрешность до $10^{-9}$. Входные данные, для которых ответ находится в диапазоне от $-3 \times 10^{-9}$ до $-1 \times 10^{-9}$, не предоставляются.
Примеры
Примеры 1
3 2 1 2 4 2 2 3 2 1
4.00
Примеры 2
3 2 1 2 2 4 2 3 1 2
HAPPY
Примечание
В примере 1, если задать $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, то выполняются условия $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ и $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$. Стоимость составляет $4.0$, и уменьшить её невозможно.
В примере 2, если задать $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, то выполняются условия $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ и $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$. Стоимость составляет $-3.0$, и так как стоимость производства может быть отрицательной, Ханбёль становится очень счастливым.