Empire가 몰락한 뒤, 은하는 경제적 불평등과 끝없는 군사 분쟁으로 암울한 시대에 접어들었다. 은하에는 $n$개의 행성이 있다. 한때 민간 선박과 수송선이 이용하던 행성 사이의 모든 보호된 초공간 항로는 잊혀졌다.

Empire를 재건하는 것을 목표로 하는 비밀 조직 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}$이다.

하지만 Empire가 몰락한 뒤 행성 사이에서 벌어진 격렬한 전투도 잊어서는 안 된다. 총 $q$번의 군사 분쟁이 있었다.

$i$번째 분쟁에서는 번호가 $L_i^1$부터 $R_i^1$까지인 행성들의 연합과 번호가 $L_i^2$부터 $R_i^2$까지인 행성들의 연합이 싸웠다. 이 분쟁의 강도는 $c_i$였다.

Empire가 몰락한 뒤의 시대는 매우 혼란스러웠으므로, 때로는 서로 싸우는 두 연합에 공통으로 속하는 행성이 있을 수도 있었다.

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$개의 줄에는 각각 $i$번째 군사 분쟁을 설명하는 다섯 정수 $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]$은 첫 번째 연합, $[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$이다.

두 번째 예제의 모든 항로의 최종 위험도는 아래 표와 같다.