Description

The railway passes through $N$ cities, each of which has a station. However, because the cities could not coordinate, each time you travel between two adjacent cities (in either direction), you must buy a separate ticket for that segment. Segment $i$ connects city $i$ and city $i+1$ ($1 \leq i < N$). If you travel farther, you need to buy multiple tickets. A paper one-way ticket for segment $i$ costs $A_i$ Boai yuan.

Although coordination fell short, the companies of each segment introduced IC cards for convenience. For segment $i$, you can pay a fee of $C_i$ Boai yuan to purchase an IC card, after which each ride on this segment only deducts $B_i$ ($B_i < A_i$) yuan. IC cards can be purchased online in advance; you do not need to buy them in the corresponding city. The card fee is non-refundable and cannot be used to buy tickets. Each card can be topped up with any amount. An IC card for segment $i$ cannot be used on other segments.

Uim needs to go on a business trip to visit $M$ cities, starting from city $P_1$ and visiting cities in the order $P_1, P_2, P_3, \cdots, P_M$. A city may be visited multiple times; consecutive cities in the sequence are not necessarily adjacent on the line, and they are guaranteed to be different.

Now he wants to know, after the trip ends, what is the minimum amount of money he will spend in total, including the cost of paper tickets, buying IC cards, and the rides paid with IC cards.

Input Format

• The first line contains two integers, $N, M$.
• The next line contains $M$ integers, representing $P_i$.
• The next $N - 1$ lines describe the segments: for segment $i$, three integers $A_i, B_i, C_i$.

Output Format

Output a single integer, the minimum total cost.

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

6394

Hint

• Buy paper tickets for $2$ to $3$ and $8$ to $9$, and buy IC cards for the others.

Constraints:

• For $30\%$ of the testdata, $M = 2$.
• For another $30\%$ of the testdata, $N \leq 1000$, $M \leq 1000$.
• For $100\%$ of the testdata, $M, N \leq 10^5$, $A_i, B_i, C_i \leq 10^5$.

Translated by ChatGPT 5