题目描述

A国有n个城市，编号依次为1,2,3....,n。有n-1条高速公路，其中，第i条高速公路连接城市 i与i+1。n个城市依次排成一条链，每条高速公路可以双向通行(费用相同)。

每条高速公路的收费各不相同，分为两种收费方式:

• 对于高速公路i，不购买年卡，单次通行价格为 $a_i$ 元。
• 对于高速公路i，购买年卡花费 $c_i$ 元，使用年卡通过该高速公路，单次通行价格 $b_i$ 元( $b_i$ < $a_i$ )。

每条高速公路的年卡是独立的，不能在其他高速公路上使用。

有一名新手货车司机，有m-1个运输任务, 从城市 $D_1$ 出发，接下来需要依次去往城市 $D_2$ , $D_3$ ,..., $D_m$ 。第j个运输任务需要从城市 $D_j$ 去往 $D_j+1$ ，可能会经过多条高速公路。

货车司机没有经验，需要你来帮助他，通过购买某些高速公路的年卡，使他完成所有运输任务所花费的费用最小。

输入格式

第一行两个整数n,m 。 接下来一行m个整数，第i个整数表示 $D_i$ 。 接下来n-1行，每行三个整数，其中第i行的三个整数依次表示第i条公路的 $a_i$ , $b_i$ , $c_i$ 。

输出格式

一个整数，表示货车司机需要花费的最少费用。

样例 #1

样例输入 #1

4 4
1 4 2 3
130 100 90
120 60 80
100 65 75

样例输出 #1

590

样例1说明：

货车司机依次走的城市:1 2 3 4 3 2 3

货车司机总花费最小的方案如下:

购买第2条高速公路 的 年卡，花去80元。

1到2不使用年卡，费用130;

2到3使用年卡，费用60;

3到4不使用年卡，费用100;

4到3不使用年卡，费用100;

3到2使用年卡，费用60;

2到3使用年卡，费用60。

总花费为590。