#P18101. Cost of Conflicts

Cost of Conflicts

Cost of Conflicts

帝国覆灭后,银河系陷入了经济不平等和军事冲突之中。第二基地希望恢复星球间的安全航线,使任意两个星球之间都能互相到达。

共有 nn 个星球,按经济水平严格递增的顺序编号。第 vv 个星球的经济水平是整数 ava_v,满足 a1<a2<⋯<ana_1<a_2<\cdots<a_n。

任意两个不同星球 u,vu,v 之间都可以建立一条无向航线。它最初的危险程度是

max⁡(au,av)min⁡(au,av).\frac{\max(a_u,a_v)}{\min(a_u,a_v)}.

过去共发生过 qq 次军事冲突。第 ii 次冲突的两方分别由编号在区间 [Li1,Ri1][L_i^1,R_i^1] 和 [Li2,Ri2][L_i^2,R_i^2] 中的星球组成,冲突强度为 cic_i。这两个区间可以相交。

若一条航线的两个端点满足以下至少一个条件,它的危险程度就乘以 cic_i:

  • u∈[Li1,Ri1]u\in[L_i^1,R_i^1] 且 v∈[Li2,Ri2]v\in[L_i^2,R_i^2];
  • u∈[Li2,Ri2]u\in[L_i^2,R_i^2] 且 v∈[Li1,Ri1]v\in[L_i^1,R_i^1]。

对于同一次冲突,一条航线至多乘一次 cic_i,即使上述两个条件同时成立。不同冲突的作用则相互独立,所有适用的乘数都要累乘。

求出使所有星球连通所需的航线危险程度总和的最小值。也就是说,求这个完全无向图的最小生成树权值。如果答案大于 10910^9,则输出 10910^9。

输入格式

第一行两个整数 n,qn,q(1≤n≤1051\le n\le10^5,0≤q≤1050\le q\le10^5)。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤av≤1071\le a_v\le10^7),保证严格递增。

接下来 qq 行,第 ii 行包含五个整数 Li1,Ri1,Li2,Ri2,ciL_i^1,R_i^1,L_i^2,R_i^2,c_i,满足

$$1\le L_i^1\le R_i^1\le n,\qquad 1\le L_i^2\le R_i^2\le n,\qquad1\le c_i\le10^5.$$

输入只有一组数据。

输出格式

输出一个实数,表示最小生成树权值与 10910^9 中的较小者。

你的答案与正确答案的绝对误差或相对误差不超过 10−410^{-4} 即视为正确。

样例 1

4 0
1 2 5 10
6.5

没有冲突,选择航线 (1,2),(2,3),(3,4)(1,2),(2,3),(3,4),危险程度总和为 2+2.5+2=6.52+2.5+2=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
35.5

可以选取 (1,2),(1,3),(1,4),(4,5)(1,2),(1,3),(1,4),(4,5),权值分别为 1.5,6,10,181.5,6,10,18。

样例 3

4 3
1 2 4 8
1 4 1 4 2
1 4 1 4 3
1 4 1 4 5
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
1000000000