Train Travel

Interview

Time limit1sMemory limit256 MB

Summary

Count how many times each rail is crossed and pay the cheaper of single tickets or a discount card plus cheap fares for every rail.

Level: Medium4 of 10
Topics: Prefix sum, Greedy
Solved: No attempts yet

Problem

There are $N$ cities on a line numbered $1$ to $N$ . Rail $i$ connects cities $i$ and $i+1$ bidirectionally.

For each rail you may pay ticket fare $A_i$ per ride, or buy a rail-specific IC card for $C_i$ once and pay $B_i$ per ride on that rail ( $A_i > B_i$ ). You start with no cards.

You visit cities $P_1, P_2, \ldots, P_M$ in order, moving from $P_j$ to $P_{j+1}$ on day $j$ . Minimize total spending on card purchases plus rides.

Input

Line 1: $N$ , $M$ . Line 2: $P_1, \ldots, P_M$ . Next $N-1$ lines: $A_i$ , $B_i$ , $C_i$ for rail $i$ .

Output

Print the minimum total cost.

Constraints

$2 \leq N, M \leq 100000$ , $1 \leq B_i < A_i \leq 100000$ , $1 \leq C_i \leq 100000$ , $1 \leq P_j \leq N$ , and $P_j \neq P_{j+1}$ .

Examples4

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3
Input
```
3 2
1 3
10 5 100
10 5 1
```
Expected output
```
16
```
Example 4
Input
```
3 3
1 2 3
10 5 100
10 5 1
```
Expected output
```
16
```