LG#P3406. 海底高铁

海底高铁

P3406 海底高铁

题目描述

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

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

\hspace{15pt}Uim 现在需要出差,要去 mm 个城市,从城市 p1p_1 出发分别按照 p1,p2,p3,⋯ ,pmp_1,p_2,p_3,\cdots,p_m 的顺序访问各个城市,可能会多次访问一个城市,且相邻访问的城市位置不一定相邻,而且不会是同一个城市。

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

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(2 \leqq n \leqq 10^5;\ 2 \leqq m \leqq 10^5\right)$ 代表城市数量与需要访问的城市数量。

\hspace{15pt}第二行输入 mm 个整数 p1,p2,…,pm(1≦pi≦n)p_1,p_2,\dots,p_m \left(1 \leqq p_i \leqq n\right) 代表访问城市的顺序,保证相邻两次访问的城市不同。

\hspace{15pt}此后 n−1n-1 行,第 ii 行输入三个整数 $a_i,b_i,c_i \left(1 \leqq b_i < a_i \leqq 10^5;\ 0 \leqq c_i \leqq 10^5\right)$ 代表第 ii 段铁路的纸质单程票价格、IC 卡单次扣费与 IC 卡工本费。

输出格式

\hspace{15pt}在一行上输出一个整数,代表出差结束后的最少总花费。

测试样例

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
6394

样例 1 解释

\hspace{15pt}第 22 段铁路(连接城市 22 和城市 33)与第 88 段铁路(连接城市 88 和城市 99)购买纸质车票,其余铁路购买 IC 卡。

数据范围与提示

∙ \hspace{23pt}\bullet\,对于 30%30\% 的数据,m=2m=2;

∙ \hspace{23pt}\bullet\,对于另外 30%30\% 的数据,n≦1000n \leqq 1000,m≦1000m \leqq 1000;

∙ \hspace{23pt}\bullet\,对于 100%100\% 的数据,2≦n,m≦1052 \leqq n, m \leqq 10^5,1≦bi<ai≦1051 \leqq b_i < a_i \leqq 10^5,0≦ci≦1050 \leqq c_i \leqq 10^5。