AT_joi2015ho_a 鉄道旅行 (Railroad Trip)

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

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

## 任务 给定 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$。 由 ChatGPT 4.1 翻译