题目描述

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$ 日元。
• 乘坐铁路 $i$ 时，使用 IC 卡的票价为 $B_i$ 日元。但要用 IC 卡乘坐铁路 $i$，需要事先购买该铁路专用的 IC 卡，购买费用为 $C_i$ 日元。已购买的 IC 卡可以无限次使用。
• 由于 IC 卡结算更方便，IC 卡乘坐铁路的票价总是低于纸质车票，即对于所有 $i=1,2,\ldots,N-1$，都有 $A_i > B_i$。
• 每条铁路的 IC 卡互不通用，即铁路 $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 卡票价 $B_i$，以及该铁路 IC 卡的购买费用 $C_i$。

输出格式

输出一个整数，表示本次旅行的最小总花费（日元）。

输入输出样例 #1

输入 #1

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

输出 #1

550

输入输出样例 #2

输入 #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

说明/提示

任务

给定 JOI 国的城市数量、旅行路线，以及每条铁路的票价和 IC 卡价格，编写程序求出本次旅行的最小总花费。

限制

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

• $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

在本例中，最优的旅行方案如下：

• 购买铁路 $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$。