题目描述

山城作为陪都，被进行了长达 $6$ 年又 $10$ 个月的无差别轰炸，轰炸形成了一个巨大迷宫。这个迷宫一共有 $n$ 个洞穴，洞穴之间有很多单向隧道。经过分析，可以发现：这些隧道能被分为 $m$ 组，对于每一组，编号在区间 $[s_l,s_r]$ 内的每一个洞穴，与编号在区间 $[t_l,t_r]$ 内的每一个洞穴之间，都有一条隧道，每组内共有 $(s_r-s_l+1)\cdot(t_r-t_l+1)$ 条隧道，通过同组内每一条隧道的时间都相等。

为了进一步节约时间，小 Z 可以挖掘新的隧道，但是，每个洞穴的性质不同，导致挖掘隧道的难度不同，有些洞穴甚至无法挖掘隧道。具体来说，第 $i$ 个洞穴有一个值 $v_i$，$v_i=0$ 表示无法挖掘隧道，对于其它值，表示从第 $i$ 个洞穴开始，挖掘一条到第 $j$ 个洞穴的隧道，并到达第 $j$ 个隧道，需要花费 $|i-j|\cdot v_i$ 时间。

小 Z 希望在最短时间内到达第 $n$ 个洞穴，决定不限制挖掘隧道的数量，现在，你需要告诉小 Z 最少需要用的时间。

简化题意： 存在 $n$ 个点和两种有向边：

• 一类边分 $m$ 组，每组的边权相同，从 $[s_l,s_r]$ 中的所有点连向 $[t_l,t_r]$ 中的所有点。
• 二类边存在于任意两点 $i,j$ 间，从 $i$ 连向 $j$ 的二类边的边权为 $|i-j|\times v_i$。注意：$v_i=0$ 表示 $i$ 不能连向其他点。

求从点 $1$ 到点 $n$ 的最短路。

输入格式

第一行两个整数 $n,m$。

接下来一行 $n$ 个整数 $v_1,v_2,\ldots,v_n$。

接下来 $m$ 行，每行描述一组隧道。

每行 $5$ 个整数 $s_l,s_r,t_l,t_r,w$，其中 $w$ 表示通过时间。

输出格式

如果无解，则只需输出一行一个整数 -1。

如果有解，则输出一行一个整数 $t$，表示最少花费的时间。

样例输入

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

样例输出

9

样例解释

$1$ 号到 $2$ 号走第一组隧道，$2$ 号到 $6$ 号挖掘隧道，用时 $1\times(6-2)=4$。

也可以，$1$ 号到 $3$ 号走第一组隧道，$3$ 号到 $4$ 号挖掘隧道，用时 $2\times(4-3)=2$，$4$ 号到 $6$ 号走第二组隧道。

数据范围

对于 $100\%$ 的数据，有 $1\le w,v_i\le10^9$。