Minimizing Railway Travel Expenses

You are given a railway line that passes through $N$ cities numbered from $1$ to $N$. Each city has one station. The railway consists of $N-1$ segments; the $i$-th segment connects city $i$ and city $i+1$ for $1\le i<N$.

For each segment $i$, you have two options for paying for a ride:

• Buy a paper ticket for the segment with cost $A_i$ per ride.
• Purchase an IC card for segment $i$ with a one-time manufacturing fee of $C_i$, after which each ride costs $B_i$ (with $B_i < A_i$). Note that the manufacturing fee is non-refundable and one IC card can only be used on its designated segment.

A traveler has a business trip itinerary visiting $M$ cities in order: $P_1, P_2, \dots, P_M$. The journey may visit some cities multiple times and the consecutive cities are not necessarily adjacent; however, consecutive cities are always different. To travel between two arbitrary cities $u$ and $v$, the traveler must use all segments on the unique path between them along the railway. Formally, if $u < v$, the traveler must pass every segment $i$ for $u \le i v$.

Your task is to determine the minimum total cost incurred for the entire trip, including the cost of buying paper tickets or the cost of IC card fees plus recharges.

For each segment $i$, if it is used $k_i$ times during the trip, you can pay either:

• Paper tickets: Total cost $= k_i \times A_i$.
• IC card: Total cost $= C_i + k_i \times B_i$.

Your final answer is the sum over all segments of the chosen minimum cost for that segment.

inputFormat

The first line contains two integers $N$ and $M$ ($2\le N\le 10^5$, $2\le M\le 10^5$) representing the number of cities and the number of visited cities respectively.

The second line contains $M$ integers $P_1, P_2, \dots, P_M$ ($1\le P_i\le N$) representing the itinerary. It is guaranteed that $P_i \neq P_{i+1}$ for $1\le i < M$.

The third line contains $N-1$ integers $A_1, A_2, \dots, A_{N-1}$, where $A_i$ is the cost of a paper ticket for segment $i$.

The fourth line contains $N-1$ integers $B_1, B_2, \dots, B_{N-1}$, where $B_i$ is the per-ride cost using an IC card for segment $i$ ($B_i < A_i$).

The fifth line contains $N-1$ integers $C_1, C_2, \dots, C_{N-1}$, where $C_i$ is the one-time manufacturing fee of the IC card for segment $i$.

outputFormat

Output a single integer --- the minimum total cost of the trip.

sample

4 3
1 3 4
10 10 10
5 5 5
3 3 3

24