← 返回题目列表

AtCoder · joi2015ho_a

A. 铁路旅行

中文机器翻译题面 查看原题

配点: 100 点

在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 这是日元。 使用IC卡乘坐
  • 鉄道 i 的票价为 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卡的费用与您乘坐的火车票价的总和。

課題

给出了JOI国家的城市数量、行程行程以及每个JOI国家的火车票价和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 行。


制限

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

  • 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 点]

没有其他限制。


入力例 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 ,然后前往市区。 使用IC卡移动至 2 来自城市 乘坐火车前往 3 。这包括 使用IC卡前往 120 + 50 = 170 花费日元。
  • 2 当天,本市 使用纸质车票前往 3 来自城市 乘坐火车前往 2 。这包括 使用IC卡前往 50 花费日元。
  • 3 当天,本市 使用纸质车票前往 2 来自城市 乘坐火车前往 3 ,然后前往市区。 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