4100. 寻宝（弱化版）

【题目背景】

HS玩原审玩傻了，决定去提瓦特大陆寻宝

【题目描述】

HS进入了一个迷宫

这个迷宫一共有n个洞穴，洞穴之间有很多单向隧道，很难数清，但经过调查发现，这些隧道可以分为m组，对于每一组，编号在区间[sl,sr]内的每一个洞穴，与编号在区间[tl,tr]内的每一个洞穴之间，都有一条隧道，通过同组内每一条隧道的时间都相等

但HS急于玩原审，开始徒手挖掘隧道

每个洞穴的性质不同，导致挖掘隧道的难度不同，有些洞穴甚至无法挖掘隧道，具体来说，第i个洞穴有一个值vi，vi=0表示无法挖掘隧道，对于其它值，表示从第i个洞穴开始，挖掘一条到第j个洞穴的隧道，并到达第j个隧道，需要花费∣i−j∣∗vi时间

HS希望从第一个节点以最少的时间内到达点n，请你帮他求出最短时间

【输入格式】

第一行两个整数n，m

第二行n个整数表示v1到vn

接下来m行，每行五个整数sl,sr,tl,tr,w，w表示通过单向通道的时间

【输出格式】

因为出题人太菜了不会写spj，你只需要输出最短时间就行了,若无解，输出-1，对于加强版可以看下方原题链接

【样例输入】

6 2



0 1 2 0 0 0



1 1 2 3 5



4 5 6 6 2

【样例输出】

 9

【样例说明】

在此键入。

【数据规模与约定】

n,m<=5e4

v,w<=1e6

不存在部分分和数据规模梯度

原题时间限制2s，但由于本题数据全随机过弱，所以时间限制调为1s

【来源】

洛谷P5508寻宝

https://www.luogu.com.cn/problem/P5508