Problem Description

In JOI Kingdom, there are $ N $ cities numbered $1, 2, \ldots, N$. There are also $ N - 1 $ railroads numbered $1, 2, \ldots, N - 1$. Railroad $ i $ ($1 \leq i \leq N - 1$) connects city $ i $ and city $ i + 1 $ bidirectionally.

There are two ways to ride the railroads in JOI Kingdom: using a paper ticket or using an IC card.

• The fare for railroad $ i $ using a paper ticket is $ A_i $ yen.
• The fare for railroad $ i $ using an IC card is $ B_i $ yen. However, to use an IC card on railroad $ i $, you need to purchase the IC card for railroad $ i $ in advance. The cost to purchase the IC card for railroad $ i $ is $ C_i $ yen. Once purchased, the IC card can be used multiple times.

Since the IC card simplifies the fare processing, the fare using an IC card is cheaper than using a paper ticket. That is, for $i = 1, 2, \ldots, N - 1$, $ A_i > B_i $ holds. The specifications of the IC cards are different for each railroad, so an IC card purchased for one railroad cannot be used on any other railroad.

You have decided to travel throughout JOI Kingdom. You will start from city $ P_1 $ and visit cities $P_2, P_3, \ldots, P_M$ in order. The trip consists of $ M - 1 $ days. On day $ j $ ($1 \leq j \leq M - 1$), you will move from city $ P_j $ to city $ P_{j + 1 } $ by train. This may involve transferring between several railroads. It is also possible to visit the same city more than once. The railroads in JOI Kingdom are fast, so you can move from any city to any other city in one day.

Currently, you do not have any IC cards for the railroads. You want to purchase some IC cards in advance to minimize the total cost of the trip, which includes the cost of purchasing the IC cards and the fares for the railroads you ride.

Input Format

Read the following data from standard input:

• The first line contains two integers $ N $ and $ M $ separated by a space. These indicate that there are $ N $ cities in JOI Kingdom and the trip consists of $ M - 1 $ days.
• The second line contains $ M $ integers $P_1, P_2, \ldots, P_M$ separated by spaces. These indicate that on day $ j $ ($1 \leq j \leq M - 1$), you will move from city $ P_j $ to city $ P_{j + 1} $.
• The next $ N - 1 $ lines contain three integers $ A_i, B_i, C_i $ separated by spaces. These indicate that the fare for railroad $ i $ using a paper ticket is $ A_i $ yen, the fare using an IC card is $ B_i $ yen, and the cost of the IC card for railroad $ i $ is $ C_i $ yen.

Output Format

Output the minimum total cost of the trip in yen as a single integer on standard output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

550

Sample Input #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

Sample Output #2

81

Notes/Hints

Task

Given the number of cities in JOI Kingdom, the itinerary of the trip, and the fares and IC card prices for each railroad, write a program to find the minimum total cost of the trip.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [20 points]

Satisfies the following conditions:

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

Subtask 2 [30 points]

Satisfies the following conditions:

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

Subtask 3 [50 points]

No additional constraints.

Sample Explanation 1

In this case, the way to minimize the total cost of the trip is as follows:

• Purchase the IC cards for railroad $ 2 $ and railroad $ 3 $. This costs $ 80 + 130 = 210 $ yen.
• On the first day, move from city $ 1 $ to city $ 2 $ using a paper ticket, then from city $ 2 $ to city $ 3 $ using an IC card. This costs $ 120 + 50 = 170 $ yen.
• On the second day, move from city $ 3 $ to city $ 2 $ using an IC card. This costs $ 50 $ yen.
• On the third day, move from city $ 2 $ to city $ 3 $ using an IC card, then from city $ 3 $ to city $ 4 $ using an IC card. This costs $ 50 + 70 = 120 $ yen.

By moving this way, the total cost of the trip is $ 210 + 170 + 50 + 120 = 550 $ yen. This is the minimum, so output $ 550 $.

见题面 Input 部分

见题面 Output 部分