题目描述

译自 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$ 元。

---

输出格式

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

---

样例 1

输入

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

输出

550

解释： 在这种情况下，旅行总花费最小的方案如下：

• 购买铁路 $2$ 和 $3$ 的 IC 卡。花去 $80 + 130 = 210$ 元。
• 第一天，使用纸质车票从城市 $1$ 到城市 $2$，然后使用 IC 卡从城市 $2$ 到 $3$。花去 $120 + 50 = 170$ 元。
• 第二天，使用 IC 卡从城市 $3$ 到城市 $2$。花去 $50$ 元。
• 第三天，使用 IC 卡从城市 $2$ 到城市 $3$，然后使用 IC 卡从城市 $3$ 到城市 $4$。花去 $50 + 70 = 120$ 元。

如果像这样乘车的话，旅行的总花费为 $210 + 170 + 50 + 120 = 550$ 元，是能够达到的最小值，因此输出 $550$。

---

样例 2

输入

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$ 分]
没有额外限制。