#P18101. Cost of Conflicts
Cost of Conflicts
Cost of Conflicts
帝国覆灭后,银河系陷入了经济不平等和军事冲突之中。第二基地希望恢复星球间的安全航线,使任意两个星球之间都能互相到达。
共有 个星球,按经济水平严格递增的顺序编号。第 个星球的经济水平是整数 ,满足 。
任意两个不同星球 之间都可以建立一条无向航线。它最初的危险程度是
过去共发生过 次军事冲突。第 次冲突的两方分别由编号在区间 和 中的星球组成,冲突强度为 。这两个区间可以相交。
若一条航线的两个端点满足以下至少一个条件,它的危险程度就乘以 :
- 且 ;
- 且 。
对于同一次冲突,一条航线至多乘一次 ,即使上述两个条件同时成立。不同冲突的作用则相互独立,所有适用的乘数都要累乘。
求出使所有星球连通所需的航线危险程度总和的最小值。也就是说,求这个完全无向图的最小生成树权值。如果答案大于 ,则输出 。
输入格式
第一行两个整数 (,)。
第二行 个整数 (),保证严格递增。
接下来 行,第 行包含五个整数 ,满足
$$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.$$输入只有一组数据。
输出格式
输出一个实数,表示最小生成树权值与 中的较小者。
你的答案与正确答案的绝对误差或相对误差不超过 即视为正确。
样例 1
4 0
1 2 5 10
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
可以选取 ,权值分别为 。
样例 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