题目描述

韩星想在毕业前，为以后加入全国大学生程序设计竞赛社团联合会的学弟学妹们捐赠一些自己制作的半导体。为了尽可能多地制作半导体，她希望最小化制造一个半导体所需的成本。

一个半导体可以表示为一张有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1$ 到 $N$，顶点 $i$ 具有实数势能 $E_i$。

其中

$$E_1=1.0, \qquad E_N=-1.0,$$

其余顶点的势能可以任意设定。

此外，顶点 $1$ 和顶点 $N$ 是特殊顶点：不存在进入顶点 $1$ 的边，也不存在从顶点 $N$ 出发的边。

半导体中的一条有向边 $e=(u,v)$ 可以从顶点 $u$ 向顶点 $v$ 分别传递正能量和负能量。

每条边具有两个能量传递效率：

• 正能量传递效率 $a_e\ge 0$；
• 负能量传递效率 $b_e\ge 0$。

若在边 $e$ 上传递正能量 $p_e\ge 0$ 和负能量 $m_e\le 0$，则该边产生的制造成本为

$$a_ep_e+b_em_e.$$

为了避免过载损坏半导体，每条边 $e=(u,v)$ 都必须满足

$$p_e+m_e\ge E_u-E_v.$$

一个半导体的制造成本等于所有边产生的成本之和。

请合理设置所有可自由选择的顶点势能，以及每条边上的 $p_e,m_e$，使半导体不发生故障，并最小化制造成本。

输入格式

第一行包含两个整数 $N,M$，分别表示顶点数和边数。

$$3\le N\le 500, \qquad 1\le M\le N(N-1)$$

接下来 $M$ 行，每行包含四个整数 $u,v,a,b$，表示存在一条从 $u$ 指向 $v$ 的边，其正能量传递效率为 $a$，负能量传递效率为 $b$。

$$1\le u,v\le N, \qquad u\ne v, \qquad 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, \quad m_{1,2}=0, \quad p_{2,3}=2, \quad m_{2,3}=0, \quad E_2=1.$$

于是

$$p_{1,2}+m_{1,2}=0\ge E_1-E_2=0,$$ $$p_{2,3}+m_{2,3}=2\ge E_2-E_3=2.$$

总成本为 $4$，且无法更低。

对于样例 2，可以取

$$p_{1,2}=3, \quad m_{1,2}=-2, \quad p_{2,3}=3, \quad m_{2,3}=-2, \quad E_2=0.$$

两条边均满足约束，总成本为 $-3$，因此输出 HAPPY。