In the country of JOI, there are $N$ cities, numbered $1, 2, \dots, N$. 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 travel on the railways in the country of JOI: using paper tickets or using IC cards.

• The fare for traveling on railway $i$ with a paper ticket is $A_i$ yen.
• The fare for traveling on railway $i$ with an IC card is $B_i$ yen. However, to travel on railway $i$ with an IC card, you must purchase an IC card that can be used for railway $i$ in advance. Purchasing an IC card for railway $i$ costs $C_i$ yen. Once purchased, an IC card can be used any number of times.

Since IC cards simplify payment, the fare for traveling with an IC card is cheaper than the fare for traveling with a paper ticket. That is, for $i = 1, 2, \dots, N-1$, $A_i > B_i$ holds. Because the specifications of IC cards differ for every railway, for any $i$, an IC card that can be used for railway $i$ cannot be used for any other railway.

You have decided to travel around the country of JOI. You plan to start at city $P_1$ and visit cities in the order $P_2, P_3, \dots, P_M$. The trip consists of an itinerary of $M-1$ days. On the $j$-th day ($1 \le j \le M-1$), you will travel from city $P_j$ to city $P_{j+1}$ by railway. During this, you may travel by connecting several railways. Also, you might visit the same city more than once. Since the railways in the country of JOI are fast, you can travel from any city to any other city in one day.

You currently do not own an IC card for any railway. You want to purchase some IC cards in advance to minimize the total cost of the trip, which is the sum of the IC card purchase costs and the fares for the railways you travel on.

Input

Read the following data from standard input:

• The first line contains two space-separated integers $N$ and $M$. These represent that there are $N$ cities in the country of JOI and the trip consists of an itinerary of $M-1$ days.
• The second line contains $M$ space-separated integers $P_1, P_2, \dots, P_M$. These represent that on the $j$-th day ($1 \le j \le M-1$), you travel from city $P_j$ to city $P_{j+1}$ by railway.
• Of the following $N-1$ lines, the $i$-th line ($1 \le i \le N-1$) contains three space-separated integers $A_i, B_i, C_i$. These represent that the fare for traveling on railway $i$ with a paper ticket is $A_i$ yen, the fare with an IC card is $B_i$ yen, and the cost to purchase an IC card for railway $i$ is $C_i$ yen.

Output

Output the minimum total cost of the trip in yen as an integer on a single line.

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 \neq P_{j+1}$ ($1 \le j \le M-1$).

Subtasks

Subtask 1 [20 points]

The following conditions are satisfied:

• $2 \le N \le 1\,000$.
• $M = 2$.
• $1 \le B_i < A_i \le 1\,000$ ($1 \le i \le N-1$).
• $1 \le C_i \le 1\,000$ ($1 \le i \le N-1$).

Subtask 2 [30 points]

The following conditions are satisfied:

• $2 \le N \le 1\,000$.
• $2 \le M \le 1\,000$.
• $1 \le B_i < A_i \le 1\,000$ ($1 \le i \le N-1$).
• $1 \le C_i \le 1\,000$ ($1 \le i \le N-1$).

Subtask 3 [50 points]

There are no additional constraints.

Examples

Input 1

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

Output 1

550

Note 1

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

• Purchase IC cards for railway 2 and railway 3. This costs $80 + 130 = 210$ yen.
• On the 1st day, travel from city 1 to city 2 using a paper ticket, then travel from city 2 to city 3 using an IC card. This costs $120 + 50 = 170$ yen.
• On the 2nd day, travel from city 3 to city 2 using an IC card. This costs $50$ yen.
• On the 3rd day, travel from city 2 to city 3 using an IC card, then travel from city 3 to city 4 using an IC card. This costs $50 + 70 = 120$ yen.

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

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

Output 2

81