题目描述

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

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

小Z现在需要出差，要去 $\red{M}$ 个城市，从城市 $\red{P_1}$ 出发分别按照 $\red{P_1，P_2，P_3，...，P_M }$的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

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

输入格式

第一行两个整数，$\red{N，M}$。

接下来一行，$\red{M}$ 个数字，表示 $\red{P_i}$。

接下来 $\red{N − 1}$ 行，表示第 $\red{i}$ 段铁路的 $\red{A_i，B_i，C_i}$。 .

输出格式

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

样例

输入数据

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

提示

$\red{2}$ 到 $\red{3}$ 以及 $\red{8}$ 到 $\red{9}$ 买票，其余买卡。

对于 $\red{30\%}$ 的数据，$\red{M = 2}$。

对于另外 $\red{30\%}$ 的数据，$\red{N ≤ 1000，M ≤ 1000}$。

对于 $\red{100\%}$ 的数据，$\red{M，N ≤ 10^5，A_i，B_i，C_i ≤ 10^5}$。