海底高铁

题目描述

大东亚海底隧道连接着厦门、新北、博艾、那霸、鹿儿岛等城市，横穿东海，耗资10001000亿博艾元，历时15年，于公元2058年建成。凭借该隧道，从厦门可以乘坐火车直达台湾、博艾和日本，全程只需要44个小时。 该铁路经过N个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第i段铁路连接了城市i和城市i+1（1≤i<N），如果搭乘距离较远，需要购买多张车票。第i段铁路购买纸质单程票需要Ai博艾元。 各段铁路公司推出了IC卡优惠：对于第i段铁路，花费Ci博艾元工本费购买IC卡后，每次乘坐该段仅需扣除Bi（Bi<Ai）元。IC卡可提前线上购买，工本费不退，且每张IC卡仅可用于对应段铁路，卡内可任意充值。 Uim需要出差，要按顺序访问M个城市P1,P2,...,PM，相邻访问的城市不相同，可能重复访问同一城市。请求出出差的总最小花费，包含纸质车票费用、IC卡工本费及充值费用总和。

输入描述

第一行两个整数N、M，分别表示城市数量和需要访问的城市数量。 第二行M个整数，表示访问顺序Pi。 接下来N-1行，每行三个整数Ai、Bi、Ci，分别表示第i段铁路的纸质票价、IC卡单次扣费、IC卡工本费。

输出描述

输出一个整数，表示最少总花费。

输入样例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

提示

• 样例解释：第2-3段、第8-9段铁路购买纸质票，其余段购买IC卡时总花费最小。
• 数据范围：
  • 30%数据满足M=2
  • 另外30%数据满足N≤1000，M≤1000
  • 100%数据满足1≤N,M≤1e5，1≤Ai,Bi,Ci≤1e5，Bi<Ai