P5508 寻宝

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

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

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

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

样例 $1$：$1$ 号到 $2$ 号走第一组隧道，$2$ 号到 $6$ 号挖掘隧道，用时 $1\times (6-2)=4$。 样例 $2$：$1$ 号到 $3$ 号走第一组隧道，$3$ 号到 $4$ 号挖掘隧道，用时 $2\times (4-3)=2$，$4$ 号到 $6$ 号走第二组隧道。 每个 Subtask 包括两个测试点，取较低分。 对于每个测试点： 如果输出格式错误，那么，该测试点得 $0$ 分。 如果你没有给出正确的用时，那么，该测试点得 $0$ 分。 如果你给出正确的用时，但没有给出方案，那么你可以得到该测试点一半的分数（每个测试点得分向下取整）。 如果你给出了错误方案，那么你可能可以得到该测试点一半的分数，或者得 $0$ 分。 如果你给出了正确的方案，那么你可以得到该测试点全部的分数。 上面两个输出都可以得到满分，还有一种方案是 $1\;2\;4\;6$。 如果你输出： ``` 9 0 ``` 那么你可以得到该测试点一半的分数。 数据范围： $0\le w,v_i \le 10^9$。 ::cute-table{tuack} Subtask | 分值| $n$ | $m$ | 特殊性质 :-: | :-: | :-: | :-: | :-: $1$ | $5$| $10^2$| $10^2$| | $2$| $10$| $3\times 10^3$| $3\times 10^3$| | $3$| $11$| $5\times 10^4$| $5\times 10^4$| $2,3$| $4$| $10$| $5\times 10^4$| $5\times 10^4$| $1$| $5$| $12$| $5\times 10^4$| $0$| | $6$| $12$| $5\times 10^4$| $1$| | $7$| $13$| $5\times 10^4$| $20$|$3$ | $8$| $13$| $5\times 10^4$| $20$| | $9$| $14$| $5\times 10^4$| $5\times 10^4$| | 特殊性质 $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。~~