After the fall of the Empire, the galaxy fell into dark times of economic inequality and endless military conflicts. There are $n$ planets in the galaxy. All protected hyperspace routes between planets, which were once used by civilian and transport ships, were forgotten.

The leaders of the Second Foundation, a secret organization whose goal is to restore the Empire, managed to make all planets agree to a truce. Their next step is to restore protected routes between the planets, so that it becomes possible to travel from any planet to any other planet.

For the convenience of planning, the Second Foundation numbered the planets from $1$ to $n$ in the order of increasing economic level. More precisely, the economic level of planet $v$ is an integer $a_v$, and it is guaranteed that $a_1 < a_2 < \ldots < a_n$.

Before building new protected routes, the Foundation estimated the danger of every possible route. At first, the danger of a route was based only on the economic inequality between its endpoints. More precisely, for two different planets $u$ and $v$, the initial danger of the route between them was equal to

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

Since the planets are numbered in increasing order of economic level, for $u<v$ this value is equal to $\frac{a_v}{a_u}$.

However, one should not forget about the violent battles that took place between the planets after the fall of the Empire. In total, there were $q$ military conflicts.

In the $i$-th conflict, the coalition of planets with numbers from $L_i^1$ to $R_i^1$ fought against the coalition of planets with numbers from $L_i^2$ to $R_i^2$. The intensity of this conflict was $c_i$.

The times after the fall of the Empire were very chaotic, so sometimes the two fighting coalitions could even have common planets.

The Second Foundation decided that these conflicts directly affect the danger of future protected routes, because after such wars the relations between planets remain bad for a long time. More precisely, for every pair of different planets $u$ and $v$, the danger of the route between them is multiplied by $c_i$ if one of the following conditions holds:

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

or

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

For one fixed conflict, the danger of the same route can be multiplied by $c_i$ at most once, even if both conditions hold at the same time. However, different conflicts are independent. If several conflicts affect the same route, all corresponding multipliers are applied.

This task turned out to be difficult even for the geniuses of the Second Foundation, so they ask you for help. Find the minimum possible total danger of protected routes that is enough to connect all planets.

In other words, consider the complete undirected weighted graph on $n$ planets. The weight of an edge is the final danger of the corresponding route. You have to find the weight of a minimum spanning tree of this graph.

If this value is greater than $10^9$, then the galaxy is still far from being united. In this case, you should output $10^9$ instead.

Input

The first line contains two integers $n$ and $q$ — the number of planets and the number of military conflicts ($1\le n\le10^5$, $0\le q\le10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ — the economic levels of the planets ($1\le a_v\le10^7$, $a_1<a_2<\ldots<a_n$).

Each of the next $q$ lines contains five integers $L_i^1,R_i^1,L_i^2,R_i^2,c_i$ describing the $i$-th military conflict ($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$).

Here $[L_i^1,R_i^1]$ is the first coalition, $[L_i^2,R_i^2]$ is the second coalition, and $c_i$ is the intensity of the conflict.

Output

Output one real number — the minimum possible total danger of protected routes needed to connect all planets.

If this value is greater than $10^9$, output $10^9$ instead.

Your answer will be accepted if its absolute or relative error does not exceed $10^{-4}$.

Examples

Input 1

4 0
1 2 5 10

Output 1

6.5

Input 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

Output 2

35.5

Input 3

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

Output 3

180

Input 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

Output 4

1000000000

Note

In the first sample, there are no conflicts, so all route dangers are equal to their initial values.

The initial dangers of all routes are:

One optimal way to connect all planets is to choose the routes $(1,2)$, $(2,3)$, $(3,4)$. Their total danger is $2+2.5+2=6.5$.

In the second sample, the final dangers of all routes are shown in the table below.