Antes de graduarse, Hanbyeol quiere donar algunos semiconductores que él mismo fabricó para los estudiantes de primer año que se unirán a la asociación de clubes de programación universitaria. Para fabricar la mayor cantidad posible de semiconductores, desea minimizar el costo de producción de cada uno.
Un semiconductor tiene la forma de un grafo dirigido con $N$ vértices y $M$ aristas. Cada vértice está numerado del $1$ al $N$, y el vértice $i$ tiene una energía potencial $E_i$. La energía potencial es un valor real, con $E_1 = 1.0$ y $E_N = -1.0$ fijados, mientras que las energías potenciales de los demás vértices pueden ser determinadas arbitrariamente por Hanbyeol. Además, dado que el vértice $1$ y el vértice $N$ son vértices especiales, no existen aristas que entren al vértice $1$ ni aristas que salgan del vértice $N$.
Cada arista $e = (u, v)$ que compone el semiconductor puede transmitir energía positiva y negativa desde el vértice $u$ hasta el vértice $v$. Cada arista del semiconductor tiene un valor llamado eficiencia de transferencia de energía. Si Hanbyeol envía una cantidad de energía positiva $p_e (\ge 0)$ y una cantidad de energía negativa $m_e (\le 0)$ a través de una arista con eficiencia de transferencia de energía positiva $a_e (\ge 0)$ y eficiencia de transferencia de energía negativa $b_e (\ge 0)$, la cantidad de energía transmitida por la arista es $(a_e p_e + b_e m_e)$. Sin embargo, si la energía enviada a la arista $e = (u, v)$ no satisface $p_{(u,v)} + m_{(u,v)} \ge E_u - E_v$, el semiconductor podría averiarse debido a una sobrecarga.
El costo de producción del semiconductor es igual a la suma de la energía transmitida por cada arista que lo compone. Ayuda a Hanbyeol, quien intenta hacer una buena obra, a ajustar adecuadamente la energía potencial de cada vértice y la cantidad de energía enviada a cada arista para que el semiconductor no se averíe y el costo de producción sea mínimo.
Entrada
En la primera línea se proporcionan el número de vértices $N$ y el número de aristas $M$ separados por un espacio. ($3 \le N \le 500$; $1 \le M \le N(N - 1)$)
A partir de la segunda línea, se proporcionan $M$ líneas con la información de las aristas que componen el semiconductor, cada una con 4 números enteros $u, v, a, b$ separados por espacios. Esto significa que existe una arista que va del vértice $u$ al vértice $v$, con una eficiencia de transferencia de energía positiva $a$ y una eficiencia de transferencia de energía negativa $b$. No se proporcionan entradas con aristas duplicadas. ($1 \le u, v \le N$; $u \neq v$; $0 \le a, b \le 10^9$)
Salida
Imprime el costo mínimo de producción de un semiconductor. Sin embargo, si el costo de producción puede ser menor a $-3 \times 10^{-9}$, imprime HAPPY, la palabra que expresa el estado de ánimo de Hanbyeol al poder ganar dinero cada vez que produce un semiconductor. Se permite un error absoluto/relativo de hasta $10^{-9}$, y no se proporcionarán entradas donde la respuesta esté entre $-3 \times 10^{-9}$ y $-1 \times 10^{-9}$.
Ejemplos
Entrada 1
3 2 1 2 4 2 2 3 2 1
Salida 1
4.00
Entrada 2
3 2 1 2 2 4 2 3 1 2
Salida 2
HAPPY
Nota
En el ejemplo 1, si se especifica $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, se satisface $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ y $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$. El costo es $4.0$, y no es posible reducir el costo más allá de esto.
En el ejemplo 2, si se especifica $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, se satisface $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ y $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$. El costo es $-3.0$, y como el costo de producción puede ser negativo, Hanbyeol se vuelve muy feliz.