帝国灭亡后，银河系陷入了经济不平等和无休止军事冲突的黑暗时代。银河系中有 $n$ 颗行星。所有曾经供民用飞船和运输飞船使用的行星间受保护超空间航线都已被遗忘。

Second Foundation 是一个以重建帝国为目标的秘密组织，其领导者成功让所有行星同意休战。他们的下一步是恢复行星之间的受保护航线，使得从任意行星前往任意其他行星成为可能。

为方便规划，Second Foundation 按经济水平递增的顺序，将行星编号为 $1$ 到 $n$。更准确地说，行星 $v$ 的经济水平是整数 $a_v$，并且保证 $a_1<a_2<\cdots<a_n$。

在建造新的受保护航线之前，Foundation 估计了每一条可能的航线的危险程度。最初，航线的危险程度仅取决于其两个端点之间的经济差距。更准确地说，对于两颗不同的行星 $u$ 和 $v$，它们之间航线的初始危险程度等于

$$\frac{\max(a_u,a_v)}{\min(a_u,a_v)}.$$

由于行星按经济水平递增的顺序编号，当 $u<v$ 时，该值等于 $\frac{a_v}{a_u}$。

然而，也不能忘记帝国灭亡后行星之间发生的激烈战争。总共发生过 $q$ 次军事冲突。

在第 $i$ 次冲突中，编号从 $L_i^1$ 到 $R_i^1$ 的行星组成的联盟，与编号从 $L_i^2$ 到 $R_i^2$ 的行星组成的联盟交战。这次冲突的强度为 $c_i$。

帝国灭亡后的时代十分混乱，因此有时两个交战联盟甚至可能包含共同的行星。

Second Foundation 认为，这些冲突会直接影响未来受保护航线的危险程度，因为这样的战争发生后，行星之间的关系会在很长时间内保持恶劣。更准确地说，对于每一对不同的行星 $u$ 和 $v$，如果满足以下条件之一，它们之间航线的危险程度就会乘以 $c_i$：

$$u\in[L_i^1,R_i^1]\ \text{且}\ v\in[L_i^2,R_i^2],$$

或

$$u\in[L_i^2,R_i^2]\ \text{且}\ v\in[L_i^1,R_i^1].$$

对于某一次固定的冲突，同一条航线的危险程度至多乘以一次 $c_i$，即使两个条件同时成立也是如此。然而，不同冲突之间相互独立。如果多次冲突影响同一条航线，则所有相应的乘数都会生效。

这项任务甚至对 Second Foundation 的天才们而言也十分困难，因此他们向你求助。求出足以连接所有行星的受保护航线的最小可能危险程度总和。

换句话说，考虑由 $n$ 颗行星构成的完全无向带权图。每条边的权值是相应航线的最终危险程度。你需要求出这张图的最小生成树的权值。

如果这个值大于 $10^9$，那么银河系离统一仍然很远。在这种情况下，应改为输出 $10^9$。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示行星数量和军事冲突次数（$1\le n\le10^5$，$0\le q\le10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各行星的经济水平（$1\le a_v\le10^7$，$a_1<a_2<\cdots<a_n$）。

接下来的 $q$ 行中，每行包含五个整数 $L_i^1,R_i^1,L_i^2,R_i^2,c_i$，描述第 $i$ 次军事冲突（$1\le L_i^1\le R_i^1\le n$，$1\le L_i^2\le R_i^2\le n$，$1\le c_i\le10^5$）。

这里，$[L_i^1,R_i^1]$ 是第一个联盟，$[L_i^2,R_i^2]$ 是第二个联盟，$c_i$ 是冲突的强度。

输出格式

输出一个实数，表示连接所有行星所需的受保护航线的最小可能危险程度总和。

如果该值大于 $10^9$，则改为输出 $10^9$。

如果答案的绝对误差或相对误差不超过 $10^{-4}$，则会被接受。

样例

输入格式 1

4 0
1 2 5 10

输出格式 1

6.5

输入格式 2

5 4
2 3 6 10 30
1 3 3 5 2
2 4 4 5 3
1 1 5 5 5
2 5 2 5 2

输出格式 2

35.5

输入格式 3

4 3
1 2 4 8
1 4 1 4 2
1 4 1 4 3
1 4 1 4 5

输出格式 3

180

输入格式 4

5 4
1 2 3 4 10000000
1 4 1 4 100000
1 2 5 5 100000
3 3 5 5 100000
4 4 5 5 100000

输出格式 4

1000000000

说明

在第一个样例中，没有冲突，因此所有航线的危险程度都等于其初始值。

所有航线的初始危险程度如下：

一种连接所有行星的最优方法是选择航线 $(1,2)$、$(2,3)$、$(3,4)$。它们的危险程度总和为 $2+2.5+2=6.5$。

在第二个样例中，所有航线的最终危险程度如下表所示。