2724 「JOI 2015 Final」铁路旅行

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

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

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

• 购买铁路 $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\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$ 分]

没有额外限制。