说明

JOI 国有 $N$ 个城市，编号分别为 $1, 2, \dots, N$。此外，有 $N-1$ 条铁路，编号分别为 $1, 2, \dots, 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 卡乘车的票价低于使用纸质车票的票价。也就是说，对于所有 $i=1,2,\dots,N-1$，均有 $A_i > B_i$ 成立。每条铁路的 IC 卡规格完全不同，因此对于任何 $i$，能在铁路 $i$ 上使用的 IC 卡都不能用于其他铁路。

你计划周游 JOI 国。你将从城市 $P_1$ 出发，并按照 $P_2, P_3, \dots, P_M$ 的顺序访问城市。旅行由 $M-1$ 天的行程组成。在第 $j$ 天 ($1 \le j \le M-1$)，你将从城市 $P_j$ 乘坐铁路前往城市 $P_{j+1}$。此时，可能需要换乘多条铁路。此外，你可能会多次访问同一个城市。JOI 国的铁路速度很快，因此任何两个城市之间都可以在一天内到达。

目前，你没有持有任何铁路的 IC 卡。你希望提前购买一些铁路的 IC 卡，使得这次旅行的总花费（即 IC 卡购买费用与乘坐铁路的票价之和）尽可能少。

任务

给定 JOI 国的城市数量、旅行行程以及每条铁路的票价和 IC 卡价格。请编写一个程序，计算旅行总花费的最小值。

输入格式

从标准输入读取以下数据。

• 第一行包含两个以空格分隔的整数 $N, M$。它们分别表示 JOI 国有 $N$ 个城市，旅行包含 $M-1$ 天的行程。
• 第二行包含 $M$ 个以空格分隔的整数 $P_1, P_2, \dots, 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$ 日元，购买能在铁路 $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

提示

样例解释 1

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

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

按照这种方式移动，旅行总花费为 $210 + 170 + 50 + 120 = 550$ 日元。这是最小值，因此输出 $550$。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 100\,000$。
• $2 \le M \le 100\,000$。
• $1 \le B_i < A_i \le 100\,000$ ($1 \le i \le N-1$)。
• $1 \le C_i \le 100\,000$ ($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 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成