鉄道旅行 (Railroad Trip)

JOI国有 $N$ 个城市，编号从 $1$ 到 $N$ ；另外，有 $N−1$ 条铁路，编号从 $1$ 到 $N−1$ ，其中第 $i$ 条 $(1\le i\le N-1)$ 铁路双向连接城市 iii 和城市 $i+1$ 。 乘坐 JOI 国家的铁路有两种方法：用纸质车票乘车或用 IC 卡乘车。 用纸质车票在铁路 $i$ 上乘车的费用为 $A_i$ ，用 IC 卡在铁路 $i$ 上乘车的费用为 $B_i$ 。但是要用 IC 卡在铁路铁路 $i$ 上乘车，必须先购买铁路 $i$ 可以使用的 IC 卡。购买铁路 $i$ 可以使用的 IC 卡需要 $C_i$ 日元。购买一次 IC 卡就可以多次使用。 由于 IC 卡的金额处理比较简单，所以用 IC 卡乘车时的费用比用纸质车票乘车时的费用便宜。也就是说，对于所有 $1 \le i \le n-1$ ，都满足 $A_i \gt B_i$ 。由于 IC 卡的规定在每条铁路上都不同，所以对于所有 $1 \le i \le n-1$ ，不能在其他铁路上使用铁路 $i$ 可以使用的 IC 卡。 您决定在 JOI 国旅行。从城市 $P_1$ 出发，按照 $P_2,P_3...P_M$ 的顺序访问城市。旅行由 $M−1$ 天的行程组成。其中，在第 $j$ 天 $(1\le j\le M-1)$ ，在铁路上乘车从城市 $P_j$ 移动到城市$P_{j+1}$ 。此时，你可能在不同的铁路上乘车。另外，你可能会去同一个城市两次及以上。 JOI 国的铁路很快，所以你从任意一个城市乘车到任意一个城市只需要一天。现在，你没有任何铁路的 IC 卡。你可以选择预先购买一些铁路的 IC 卡，减少花费在乘车上的费用。 也就是说，你需要规划是否购买 IC 卡，使得购买 IC 卡的费用和乘车费用之和最小。

[problemUrl]: https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_a JOI 国には $ N $ 個の都市があり，それぞれ $ 1,\ 2,\ \ldots,\ N $ の番号が付けられている．また，鉄道が $ N\ -\ 1 $ 本あり，それぞれ $ 1,\ 2,\ \ldots,\ N\ -\ 1 $ の番号が付けられている．鉄道 $ i $ ($ 1\ \leqq\ i\ \leqq\ 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,\ \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\ \leqq\ j\ \leqq\ M\ -\ 1 $) に都市 $ P_j $ から都市 $ P_{j\ +\ 1} $ に鉄道で移動する．この際，いくつかの鉄道を乗り継いで移動することもある．また，同じ都市を二度以上訪れることがあるかもしれない．JOI 国の鉄道は速いので，どの都市からどの都市へも $ 1 $ 日で移動することができる． あなたは現在，どの鉄道の IC カードも持っていない．あなたは，あらかじめ，いくつかの鉄道の IC カードを購入し，この旅行にかかる金額，すなわち，IC カード購入費用と乗車した鉄道の運賃の和をできるだけ少なくしたい．

標準入力から以下のデータを読み込め． - $ 1 $ 行目には，整数 $ N,\ M $ が空白を区切りとして書かれている．これらはそれぞれ，JOI 国に都市が $ N $ 個あり，旅行が $ M\ -\ 1 $ 日間の行程からなることを表す． - $ 2 $ 行目には，$ M $ 個の整数 $ P_1,\ P_2,\ \ldots,\ P_M $ が空白を区切りとして書かれている．これらは，$ j $ 日目 ($ 1\ \leqq\ j\ \leqq\ M\ -\ 1 $) に都市 $ P_j $ から都市 $ P_{j\ +\ 1} $ に鉄道で移動することを表す． - 続く $ N\ -\ 1 $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $) には，$ 3 $ つの整数 $ A_i,\ B_i,\ C_i $ が空白を区切りとして書かれている．これらはそれぞれ，鉄道 $ i $ に紙の切符で乗車したときの運賃が $ A_i $ 円，IC カードで乗車したときの運賃が $ B_i $ 円，鉄道 $ i $ で使える IC カードの金額が $ C_i $ 円であることを表す．

標準出力に，旅行にかかる金額の最小値を円単位で表す整数を $ 1 $ 行で出力せよ． - - - - - -

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

### 課題 JOI 国の都市の数，旅行の行程，および JOI 国のそれぞれの鉄道の運賃と IC カードの価格が与えられる．このとき，旅行にかかる金額の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 2\ \leqq\ M\ \leqq\ 100\,000 $． - $ 1\ \leqq\ B_i\ <\ A_i\ \leqq\ 100\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． - $ 1\ \leqq\ C_i\ \leqq\ 100\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． - $ 1\ \leqq\ P_j\ \leqq\ N $ ($ 1\ \leqq\ j\ \leqq\ M $)． - $ P_j\ \neq\ P_{j\ +\ 1} $ ($ 1\ \leqq\ j\ \leqq\ M\ -\ 1 $)． ### 小課題 #### 小課題 1 \[20 点\] 以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 1\,000 $． - $ M\ =\ 2 $． - $ 1\ \leqq\ B_i\ <\ A_i\ \leqq\ 1\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． - $ 1\ \leqq\ C_i\ \leqq\ 1\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． #### 小課題 2 \[30 点\] 以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 1\,000 $． - $ 2\ \leqq\ M\ \leqq\ 1\,000 $． - $ 1\ \leqq\ B_i\ <\ A_i\ \leqq\ 1\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． - $ 1\ \leqq\ C_i\ \leqq\ 1\,000 $ ($ 1\ \leqq\ i\ \leqq\ N\ -\ 1 $)． #### 小課題 3 \[50 点\] 追加の制限はない． - - - - - - ### Sample Explanation 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 $ と出力する． - - - - - -