Problem Description

In JOI Country, there are $N$ cities, numbered $1, 2, \dots, N$. Also, there are $N-1$ railways, numbered $1, 2, \dots, N-1$. Railway $i$ ($1 \le i \le N-1$) connects City $i$ and City $i+1$ in both directions.

There are two ways to ride trains in JOI Country: using paper tickets and using an IC card.

• When riding Railway $i$, if you use a paper ticket, the fare is $A_i$ yen.
• When riding Railway $i$, if you use an IC card, the fare is $B_i$ yen. However, to use an IC card on Railway $i$, you must buy in advance an IC card that can be used on Railway $i$. Buying one IC card usable on Railway $i$ costs $C_i$ yen. Once purchased, this IC card can be used unlimited times.

Because IC cards are easier for handling money, the fare with an IC card is cheaper than the fare with a paper ticket. That is, for all $i = 1, 2, \dots, N-1$, $A_i > B_i$ holds. The IC card specifications are completely different for each railway, so for any $i$, an IC card usable on Railway $i$ cannot be used on any other railway.

You plan to travel around JOI Country. You will start from City $P_1$, and visit cities in the order $P_2, P_3, \dots, P_M$. The trip consists of $M-1$ days. On Day $j$ ($1 \le j \le M-1$), you will travel by rail from City $P_j$ to City $P_{j+1}$. At this time, you may need to transfer across multiple railways. Also, you may visit the same city multiple times. Railways in JOI Country are very fast, so you can reach any city from any other city within one day.

Currently, you do not have any IC cards for any railway. You want to buy some railway IC cards in advance, so that the total cost of this trip (the sum of IC card purchase costs and riding fares) is as small as possible.

Task

Given the number of cities in JOI Country, the travel plan, and the fares and IC card prices for each railway, write a program to compute the minimum possible total cost of the trip.

Input Format

Read the following from standard input.

• The first line contains two integers $N, M$ separated by spaces. They represent that JOI Country has $N$ cities, and the trip has $M-1$ days.
• The second line contains $M$ integers $P_1, P_2, \dots, P_M$ separated by spaces. They mean that on Day $j$ ($1 \le j \le M-1$), you will go from City $P_j$ to City $P_{j+1}$.
• In the next $N-1$ lines, the $i$-th line ($1 \le i \le N-1$) contains three integers $A_i, B_i, C_i$ separated by spaces. They mean that on Railway $i$, the paper-ticket fare is $A_i$ yen, the IC-card fare is $B_i$ yen, and the price to buy an IC card usable on Railway $i$ is $C_i$ yen.

Output Format

Output one line to standard output containing one integer, the minimum total cost of the trip (in yen).

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

Hint

Sample Explanation 1

In this case, the plan that minimizes the total cost is as follows:

• Buy IC cards for Railway 2 and Railway 3. This costs $80 + 130 = 210$ yen.
• Day 1: travel 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.
• Day 2: travel from City 3 to City 2 using an IC card. This costs $50$ yen.
• Day 3: travel 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.

With this movement, the total cost is $210 + 170 + 50 + 120 = 550$ yen. This is the minimum, so output $550$.

Constraints

All input data satisfy the following conditions:

• $2 \le N \le 100\,000$.
• $2 \le M \le 100\,000$.
• $1 \le B_i < A_i \le 100\,000$ ($1 \le i \le N-1$)。
• $1 \le C_i \le 100\,000$ ($1 \le i \le N-1$)。
• $1 \le P_j \le N$ ($1 \le j \le M$)。
• $P_j \ne P_{j+1}$ ($1 \le j \le M-1$)。

Subtasks

Subtask 1 [20 points]

Satisfies the following conditions:

• $2 \le N \le 1000$。
• $M = 2$。
• $1 \le B_i < A_i \le 1000$ ($1 \le i \le N-1$)。
• $1 \le C_i \le 1000$ ($1 \le i \le N-1$)。

Subtask 2 [30 points]

Satisfies the following conditions:

• $2 \le N \le 1000$。
• $2 \le M \le 1000$。
• $1 \le B_i < A_i \le 1000$ ($1 \le i \le N-1$)。
• $1 \le C_i \le 1000$ ($1 \le i \le N-1$)。

Subtask 3 [50 points]

No additional constraints.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5