Tras la caída del Empire, la galaxia entró en una época oscura de desigualdad económica y conflictos militares interminables. Hay $n$ planetas en la galaxia. Todas las rutas protegidas del hiperespacio entre planetas, que antaño utilizaban las naves civiles y de transporte, quedaron olvidadas.

Los dirigentes de la Second Foundation, una organización secreta cuyo objetivo es restaurar el Empire, lograron que todos los planetas aceptaran una tregua. Su siguiente paso es restablecer las rutas protegidas entre los planetas para que sea posible viajar de cualquier planeta a cualquier otro.

Para facilitar la planificación, la Second Foundation numeró los planetas del $1$ al $n$ en orden creciente de su nivel económico. Más precisamente, el nivel económico del planeta $v$ es un entero $a_v$, y se garantiza que $a_1<a_2<\ldots<a_n$.

Antes de construir nuevas rutas protegidas, la Foundation estimó el peligro de cada ruta posible. Al principio, el peligro de una ruta se basaba únicamente en la desigualdad económica entre sus extremos. Más precisamente, para dos planetas distintos $u$ y $v$, el peligro inicial de la ruta entre ellos era igual a

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

Como los planetas están numerados en orden creciente de su nivel económico, para $u<v$ este valor es igual a $\frac{a_v}{a_u}$.

Sin embargo, no debemos olvidar las violentas batallas que tuvieron lugar entre los planetas tras la caída del Empire. En total, hubo $q$ conflictos militares.

En el $i$-ésimo conflicto, la coalición de planetas con números desde $L_i^1$ hasta $R_i^1$ luchó contra la coalición de planetas con números desde $L_i^2$ hasta $R_i^2$. La intensidad de este conflicto fue $c_i$.

La época posterior a la caída del Empire fue muy caótica, por lo que a veces las dos coaliciones enfrentadas podían incluso tener planetas en común.

La Second Foundation decidió que estos conflictos afectan directamente al peligro de las futuras rutas protegidas, porque después de estas guerras las relaciones entre los planetas siguen siendo malas durante mucho tiempo. Más precisamente, para cada par de planetas distintos $u$ y $v$, el peligro de la ruta entre ellos se multiplica por $c_i$ si se cumple alguna de las siguientes condiciones:

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

o

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

Para un conflicto fijo, el peligro de una misma ruta puede multiplicarse por $c_i$ como máximo una vez, aunque ambas condiciones se cumplan al mismo tiempo. Sin embargo, los distintos conflictos son independientes. Si varios conflictos afectan a una misma ruta, se aplican todos los multiplicadores correspondientes.

Esta tarea resultó difícil incluso para los genios de la Second Foundation, por lo que te piden ayuda. Encuentra el mínimo peligro total posible de las rutas protegidas que sea suficiente para conectar todos los planetas.

En otras palabras, considera el grafo completo no dirigido y ponderado cuyos vértices son los $n$ planetas. El peso de una arista es el peligro final de la ruta correspondiente. Debes encontrar el peso de un árbol de expansión mínimo de este grafo.

Si este valor es mayor que $10^9$, la galaxia todavía está lejos de unificarse. En ese caso, debes imprimir $10^9$ en su lugar.

Entrada

La primera línea contiene dos enteros $n$ y $q$: el número de planetas y el número de conflictos militares ($1\le n\le10^5$, $0\le q\le10^5$).

La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$: los niveles económicos de los planetas ($1\le a_v\le10^7$, $a_1<a_2<\ldots<a_n$).

Cada una de las siguientes $q$ líneas contiene cinco enteros $L_i^1,R_i^1,L_i^2,R_i^2,c_i$ que describen el $i$-ésimo conflicto militar ($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$).

Aquí, $[L_i^1,R_i^1]$ es la primera coalición, $[L_i^2,R_i^2]$ es la segunda coalición y $c_i$ es la intensidad del conflicto.

Salida

Imprime un número real: el mínimo peligro total posible de las rutas protegidas necesarias para conectar todos los planetas.

Si este valor es mayor que $10^9$, imprime $10^9$ en su lugar.

Tu respuesta se aceptará si su error absoluto o relativo no supera $10^{-4}$.

Ejemplos

Entrada 1

4 0
1 2 5 10

Salida 1

6.5

Entrada 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

Salida 2

35.5

Entrada 3

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

Salida 3

180

Entrada 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

Salida 4

1000000000

Nota

En el primer ejemplo no hay conflictos, por lo que los peligros de todas las rutas son iguales a sus valores iniciales.

Los peligros iniciales de todas las rutas son:

Una forma óptima de conectar todos los planetas es elegir las rutas $(1,2)$, $(2,3)$, $(3,4)$. Su peligro total es $2+2.5+2=6.5$.

En el segundo ejemplo, los peligros finales de todas las rutas se muestran en la siguiente tabla.