課題

JOI 国有 $N$ 个城市，分别编号为 $1, 2, \ldots, N$。此外，有 $N - 1$ 条铁路，分别编号为 $1, 2, \ldots, N - 1$。铁路 $i$ ($1 \leq i \leq N - 1$) 是双向连接城市 $i$ 和城市 $i + 1$ 的。

在 JOI 国乘坐铁路有两种方式：用纸票乘坐和用 IC 卡乘坐。

• 如果用纸票乘坐铁路 $i$，则票价为 $A_i$ 元。
• 如果用 IC 卡乘坐铁路 $i$，则票价为 $B_i$ 元。但是，要用 IC 卡乘坐铁路 $i$，需要事先购买可以在铁路 $i$ 上使用的 IC 卡，花费为 $C_i$ 元。一次购买的 IC 卡可以多次使用。

由于 IC 卡的金额处理更简单，所以用 IC 卡乘坐铁路的票价比用纸票乘坐的票价要便宜。即对于 $i = 1, 2, \ldots, N - 1$，满足 $A_i > B_i$。由于每条铁路的 IC 卡规格都不同，因此无论对于哪个 $i$，不能将在铁路 $i$ 上使用的 IC 卡用于其他铁路。

你打算游览整个 JOI 国。从城市 $P_1$ 出发，按顺序依次访问城市 $P_2, P_3, \ldots, P_M$。旅行将持续 $M - 1$ 天。第 $j$ 天 ($1 \leq j \leq M - 1$)，从城市 $P_j$ 乘坐铁路到达城市 $P_{j + 1}$。在此过程中，可能需要换乘多条铁路。也可能多次访问同一个城市。JOI 国的铁路很快，因此可以在任何两个城市之间在一天内到达。

你目前没有任何铁路的 IC 卡。你希望提前购买一些铁路的 IC 卡，以尽量减少旅行花费，即购买 IC 卡的费用和乘坐铁路的票价之和。

输入

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

• 第 1 行包含两个整数 $N, M$，以空格分隔。它们表示 JOI 国的城市数量为 $N$，旅行持续 $M - 1$ 天。
• 第 2 行包含 $M$ 个整数 $P_1, P_2, \ldots, P_M$，以空格分隔。它们表示第 $j$ 天 ($1 \leq j \leq M - 1$)，从城市 $P_j$ 乘坐铁路到达城市 $P_{j + 1}$。
• 接下来的 $N - 1$ 行中的第 $i$ 行 ($1 \leq i \leq N - 1$)，包含三个整数 $A_i, B_i, C_i$，以空格分隔。它们表示纸票乘坐铁路 $i$ 的票价为 $A_i$ 元，用 IC 卡乘坐铁路 $i$ 的票价为 $B_i$ 元，铁路 $i$ 的 IC 卡价格为 $C_i$ 元。

输出

将旅行花费的最小金额以整数表示（单位：元），在标准输出中以一行输出。

限制

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

• $2 \leq N \leq 100,000$。
• $2 \leq M \leq 100,000$。
• $1 \leq B_i < A_i \leq 100,000$ ($1 \leq i \leq N - 1$)。
• $1 \leq C_i \leq 100,000$ ($1 \leq i \leq N - 1$)。
• $1 \leq P_j \leq N$ ($1 \leq j \leq M$)。
• $P_j \neq P_{j + 1}$ ($1 \leq j \leq M - 1$)。

子任务

子任务 1 [20 分]

满足以下条件：

• $2 \leq N \leq 1,000$。
• $M = 2$。
• $1 \leq B_i < A_i \leq 1,000$ ($1 \leq i \leq N - 1$)。
• $1 \leq C_i \leq 1,000$ ($1 \leq i \leq N - 1$)。

子任务 2 [30 分]

满足以下条件：

• $2 \leq N \leq 1,000$。
• $2 \leq M \leq 1,000$。
• $1 \leq B_i < A_i \leq 1,000$ ($1 \leq i \leq N - 1$)。
• $1 \leq C_i \leq 1,000$ ($1 \leq i \leq N - 1$)。

子任务 3 [50 分]

无额外限制。

输入示例 1

4 4
1 3 2 4
120 90 100
110