Empire の崩壊後、銀河は経済格差と終わりのない軍事紛争が続く暗黒の時代に陥りました。銀河には $n$ 個の惑星があります。かつて民間船や輸送船が利用していた、惑星間の保護された超空間航路は、すべて忘れ去られてしまいました。

Empire の復興を目指す秘密組織 Second Foundation の指導者たちは、すべての惑星に休戦に合意させることに成功しました。次の目標は惑星間の保護された航路を復旧し、どの惑星からでも他のどの惑星へでも移動できるようにすることです。

計画を立てやすくするため、Second Foundation は経済水準の低い順に惑星に $1$ から $n$ までの番号を付けました。より正確には、惑星 $v$ の経済水準は整数 $a_v$ であり、$a_1<a_2<\cdots<a_n$ が保証されています。

新しい保護航路を建設する前に、Foundation は考えられるすべての航路の危険度を見積もりました。当初、航路の危険度は両端の惑星間の経済格差のみに基づいていました。より正確には、異なる 2 つの惑星 $u$ と $v$ を結ぶ航路の初期危険度は

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

でした。

惑星の番号は経済水準の低い順に付けられているため、$u<v$ の場合、この値は $\frac{a_v}{a_u}$ です。

しかし、Empire の崩壊後に惑星間で起きた激しい戦いを忘れてはいけません。軍事紛争は合計 $q$ 回ありました。

$i$ 回目の紛争では、番号が $L_i^1$ から $R_i^1$ までの惑星の連合が、番号が $L_i^2$ から $R_i^2$ までの惑星の連合と戦いました。この紛争の激しさは $c_i$ でした。

Empire 崩壊後の時代は非常に混乱していたため、戦う 2 つの連合に共通の惑星が含まれることさえありました。

このような戦争の後には惑星間の関係が長期間悪いままとなるため、Second Foundation はこれらの紛争が将来の保護航路の危険度に直接影響すると判断しました。より正確には、異なる惑星 $u$ と $v$ の各組について、次のいずれかの条件が成り立つ場合、それらを結ぶ航路の危険度に $c_i$ を掛けます。

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

または

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

ある 1 つの紛争については、両方の条件が同時に成り立つ場合でも、同じ航路の危険度に $c_i$ を掛けるのは高々 1 回です。ただし、異なる紛争は独立しています。複数の紛争が同じ航路に影響する場合、対応するすべての倍率を掛けます。

この課題は Second Foundation の天才たちにとっても難しく、彼らはあなたに助けを求めています。すべての惑星を接続するのに十分な保護航路の危険度の合計として、可能な最小値を求めてください。

言い換えると、$n$ 個の惑星を頂点とする完全無向重み付きグラフを考えます。辺の重みは対応する航路の最終的な危険度です。このグラフの最小全域木の重みを求めなければなりません。

この値が $10^9$ より大きければ、銀河が統一されるまでにはまだ長い道のりがあるということです。その場合、代わりに $10^9$ を出力してください。

入力

最初の行には、惑星の数と軍事紛争の回数を表す 2 つの整数 $n,q$ が与えられます（$1\le n\le10^5$, $0\le q\le10^5$）。

2 行目には、惑星の経済水準を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$ が与えられます（$1\le a_v\le10^7$, $a_1<a_2<\cdots<a_n$）。

続く $q$ 行のそれぞれには、$i$ 回目の軍事紛争を記述する 5 つの整数 $L_i^1,R_i^1,L_i^2,R_i^2,c_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]$ は第 1 の連合、$[L_i^2,R_i^2]$ は第 2 の連合、$c_i$ は紛争の激しさです。

出力

すべての惑星を接続するために必要な保護航路の危険度の合計の最小値を、1 つの実数として出力してください。

この値が $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 つは、航路 $(1,2),(2,3),(3,4)$ を選ぶことです。それらの危険度の合計は $2+2.5+2=6.5$ です。

2 番目の入出力例では、すべての航路の最終的な危険度は次の表のとおりです。