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$ 条铁路线，必须预先购买该铁路线专用的 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 卡价格，求旅行所需费用的最小值。
输入格式
从标准输入读取以下数据：
- 第 1 行包含两个整数 $N, M$，以空格分隔。分别表示 JOI 国有 $N$ 个城市，旅行包含 $M-1$ 段行程。
- 第 2 行包含 $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$ 日元，购买该铁路线 IC 卡的费用为 $C_i$ 日元。
输出格式
将旅行所需费用的最小值（单位：日元）作为一个整数输出到标准输出。
数据范围
所有输入数据满足以下条件：
- $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 \neq P_{j+1}$ ($1 \le j \le M-1$)
子任务
子任务 1 [20 分] 满足以下条件： $2 \le N \le 1\,000$ $M = 2$ $1 \le B_i < A_i \le 1\,000$ ($1 \le i \le N-1$) $1 \le C_i \le 1\,000$ ($1 \le i \le N-1$)
子任务 2 [30 分] 满足以下条件： $2 \le N \le 1\,000$ $2 \le M \le 1\,000$ $1 \le B_i < A_i \le 1\,000$ ($1 \le i \le N-1$) $1 \le C_i \le 1\,000$ ($1 \le i \le N-1$)
子任务 3 [50 分] 无附加限制。
样例
输入样例 1
4 4 1 3 2 4 120 90 100 110 50 80 250 70 130
输出样例 1
550
说明
在这种情况下，使旅行费用最小的方法如下：
- 购买第 2 条和第 3 条铁路线的 IC 卡。费用为 $80 + 130 = 210$ 日元。
- 第 1 天，从城市 1 到城市 2 使用纸质车票，然后从城市 2 到城市 3 使用 IC 卡。费用为 $120 + 50 = 170$ 日元。
- 第 2 天，从城市 3 到城市 2 使用 IC 卡。费用为 $50$ 日元。
- 第 3 天，从城市 2 到城市 3 使用 IC 卡，然后从城市 3 到城市 4 使用 IC 卡。费用为 $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
输出样例 2
81