寻宝

Steve成功打开了机关，发现机关后是一个巨大的迷宫

这个迷宫一共有$n$个洞穴，洞穴之间有很多单向隧道，很难数清 但经过分析，发现： 这些隧道可以分为$m$组，对于每一组，编号在区间$[s_l,s_r]$内的每一个洞穴，与编号在区间$[t_l,t_r]$内的每一个洞穴之间，都有一条隧道，每组内共有$(s_r-s_l+1)\cdot (t_r-t_l+1)$条隧道，通过同组内每一条隧道的时间都相等 为了进一步节约时间，Steve可以挖掘新的隧道 但是，每个洞穴的性质不同，导致挖掘隧道的难度不同，有些洞穴甚至无法挖掘隧道 具体来说，第$i$个洞穴有一个值$v_i$，$v_i=0$表示无法挖掘隧道，对于其它值，表示从第$i$个洞穴开始，挖掘一条到第$j$个洞穴的隧道，并到达第$j$个隧道，需要花费$|i-j|*v_i$时间 Steve希望在最短时间内到达第$n$个洞穴，决定不限制挖掘隧道的数量 现在，你需要告诉Steve最少需要用的时间 如果可能，你应帮助Steve求出一种最优方案

第一行两个整数$n,m$ 接下来一行$n$个整数$v_1,v_2,...,v_n$ 接下来$m$行，每行描述一组隧道 每行$5$个整数$s_l,s_r,t_l,t_r,w$，其中$w$表示通过时间

如果无解，则只需输出一行一个整数"-1"(不含引号) 如果有解，则按下列格式输出： 第一行一个整数$t$，表示最少花费的时间 如果你无法给出方案，在第二行输出一个整数$0$ 如果你可以给出方案，在第二行输出一个整数$c$，在第三行输出$c$个整数，依次表示一种最优方案经过的洞穴编号 你并不需要告诉Steve经过的隧道是否为挖掘出来的，或者属于哪一组

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
3
1 2 6

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
4
1 3 4 6

样例1：1号到2号走第一组隧道，2号到6号挖掘隧道，用时$1*(6-2)=4$ 样例2：1号到3号走第一组隧道，3号到4号挖掘隧道，用时$2*(4-3)=2$，4号到6号走第二组隧道 每个Subtask包括两个测试点，取较低分 对于每个测试点： 如果输出格式错误，那么，该测试点得0分 如果你没有给出正确的用时，那么，该测试点得0分 如果你给出正确的用时，但没有给出方案，那么你可以得到该测试点一半的分数（每个测试点得分向下取整） 如果你给出了错误方案，那么你可能可以得到该测试点一半的分数，或者得0分 如果你给出了正确的方案，那么你可以得到该测试点全部的分数 上面两个输出都可以得到满分，还有一种方案是$1 2 4 6$ 如果你输出： ``` 9 0 ``` 那么你可以得到该测试点一半的分数 数据范围： $1\le w,v_i \le 10^9$ Subtask | 分值| n | m| 特殊性质 :-: | :-: | :-: | :-: | :-: 1 | 5| 100| 100| | 2| 10| 3000| 3000| | 3| 11| 50000| 50000| 2,3| 4| 10| 50000| 50000| 1| 5| 12| 50000| 0| | 6| 12| 50000| 1| | 7| 13| 50000| 20|3 | 8| 13| 50000| 20| | 9| 14| 50000| 50000| | 特殊性质1：所有$v_i=0$ 特殊性质2：所有$v_i \in \{0,k\}$，$k$为常数 特殊性质3：所有$s_l=s_r,t_l=t_r$ 保证存在到达$n$号洞穴的方案 关于输出错误方案： 如果输出的$2\leq c\leq n$，经过的点以$1$开头，以$n$结尾，且中间的点都是在$(1,n)$的整数，则这组解可能是一组最优解，可以得到一半分数 否则，得0分 ~~不用担心spj会TLE/MLE~~