#2005. 海底高铁

海底高铁

海底高铁

题目描述

该铁路经过 NN 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 ii 段铁路连接了城市 ii 和城市 i+1(1i<N)i+1(1\leq i<N)。如果搭乘的比较远,需要购买多张车票。第 ii 段铁路购买纸质单程票需要 AiA_i 博艾元。

虽然一些事情没有协调好,各段铁路公司也为了方便乘客,推出了 IC 卡。对于第 ii 段铁路,需要花 CiC_i 博艾元的工本费购买一张 IC 卡,然后乘坐这段铁路一次就只要扣 Bi(Bi<Ai)B_i(B_i<A_i) 元。IC 卡可以提前购买,有钱就可以从网上买得到,而不需要亲自去对应的城市购买。工本费不能退,也不能购买车票。每张卡都可以充值任意数额。对于第 ii 段铁路的 IC 卡,无法乘坐别的铁路的车。

Uim 现在需要出差,要去 MM 个城市,从城市 P1P_1 出发分别按照 P1,P2,P3,,PMP_1,P_2,P_3,\cdots,P_M 的顺序访问各个城市,可能会多次访问一个城市,且相邻访问的城市位置不一定相邻,而且不会是同一个城市。

现在他希望知道,出差结束后,至少会花掉多少的钱,包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数,N,MN,M

接下来一行,MM 个数字,表示 PiP_i

接下来 N1N-1 行,表示第 ii 段铁路的 Ai,Bi,CiA_i,B_i,C_i

输出格式

一个整数,表示最少花费

样例 #1

样例输入 #1

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

样例输出 #1

6394

提示

2233 以及 8899 买票,其余买卡。

对于 30%30\% 数据 M=2M=2

对于另外 30%30\% 数据 N1000M1000N\leq1000,M\leq1000

对于 100%100\% 的数据 M,N105Ai,Bi,Ci105M,N\leq 10^5,A_i,B_i,C_i\le10^5