题目描述

译自 JOI 2015 Final T1「鉄道旅行」

JOI 国有 $N$ 座城市，依次编号为 $1,2,\cdots ,N$ ；还有 $N-1$ 条可双向通行的铁路，依次编号为 $1,2,\cdots ,N-1$ 。第 $i(1\le i\le N-1)$ 条铁路连接着城市 $i$ 和 $i+1$ 。

在 JOI 国有两种乘坐列车的方法：一种是使用纸质车票，另一种是使用 IC 卡。

• 对于铁路 $i$ ，用纸质车票乘车一次的价格是 $A_{i}$ 元。
• 对于铁路 $i$ ，用 IC 卡乘车一次的价格是 $B_{i}$ 元。但是，如果要用 IC 卡在第 $i$ 条铁路乘车的话，必须事先购买在第 $i$ 条铁路使用的 IC 卡。购买在第 $i$ 条铁路使用的 IC 卡需要花费 $C_{i}$ 元。只要买过一次这条铁路的 IC 卡，无论在这条铁路使用 IC 卡乘车多少次都可以。

由于用 IC 卡更容易结算费用，用 IC 卡乘车总是比用纸质车票乘车便宜。也就是说，对于 $i=1,2,\cdots ,N-1$ ，总有 $A_{i} > B_{i}$ 成立。由于各条铁路的 IC 卡规格各不相同，对于任意的 $i$ ，能在铁路 $i$ 使用的 IC 卡并不能在其他铁路上使用。

你准备在 JOI 国旅行，从城市 $P_{1}$ 出发，按照 $P_{2},P_{3},\cdots ,P_{M}$ 的顺序进行参观。行程由 $M-1$ 天组成。第 $j(1\le j\le M-1)$ 天的计划是从城市 $P_{j}$ 坐火车移动到 $P_{j+1}$ 。可能会通过一些铁路中转。而且，你有可能多次参观同一座城市。因为 JOI 国的铁路速度很快，所以无论从哪座城市到哪座城市都能在 $1$ 天之内到达。

现在你并没有任何一条铁路的 IC 卡。你想要买其中一些铁路的 IC 卡，从而使这次旅行所需的金额，也就是说，买 IC 卡和乘坐列车的费用总和最小。

任务

编写程序以输入 JOI 国的城市数、旅行的行程以及 JOI 国中每一条铁路的票价和 IC 卡价格，求出旅行所需费用的最小值。

输入格式

从标准输入输入数据，格式见下：

• 第一行是两个由空格隔开的整数 $N$ 和 $M$ ，含义如题面所述;
• 第二行是由空格隔开的 $M$ 个整数 $P_{1},P_{2},\cdots ,P_{M}$ ，表示第 $j(1\le j\le M-1)$ 天从城市 $P_{j}$ 坐火车到城市 $P_{j+1}$ ;
• 接下来 $N-1$ 行，其中第 $i(1\le i\le N-1)$ 行有三个由空格隔开的整数 $A_{i},B_{i},C_{i}$ ，分别表示对于铁路 $i$ ，用纸质车票乘车的价格为 $A_{i}$ 元，用 IC 卡乘车的价格为 $B_{i}$ 元，购买 IC 卡的价格为 $C_{i}$ 元。

输出格式

输出到标准输出，仅一行一个整数，即以元为单位的总花费最小值。

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

550

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

81

数据范围与提示

全部的输入数据满足：

• $2\le N\le 10^5$
• $2\le M\le 10^5$
• $1\le B_{i} < A_{i}\le 10^5(1\le i \le N-1)$
• $1\le C_{i}\le 10^5(1\le i \le N-1)$
• $1\le P_{j}\le N(1\le j \le M)$
• $P_{j}\ne P_{j+1}(1\le j\le M-1)$

子任务 1 [$20$ 分]

满足以下条件：

• $2\le N \le 1000$
• $M=2$
• $1\le B_{i} < A_{i}\le 1000(1\le i \le N-1)$
• $1\le C_{i}\le 1000(1\le i \le N-1)$

子任务 2 [$30$ 分]

满足以下条件：

• $2\le N \le 1000$
• $2\le M \le 1000$
• $1\le B_{i} < A_{i}\le 1000(1\le i \le N-1)$
• $1\le C_{i}\le 1000(1\le i \le N-1)$

子任务 3 [$50$ 分]

没有额外限制。