Description
Stepmania is a widely played game among otakus. Mr. SuBaRaSi has always wanted to become an otaku.
So he wanted to be a maestro in Stepmania. However, it would take a lot of time to practice.
For each song, some parts are difficult while other parts are easy. For example, the chorus at the middle part of the song
might be hard that he need to practice 25 times in order to get familiar. On the other hand, the intro part might be easy that he
only need to practice 5 times.
He found it is NOT efficient to always practice from the start all the way to the end of the song. As in the previous example,
he can start at the chorus part till the end for 20 times, and from intro to the end 5 times, which might be more efficient.
However, since is not good for him to interrupt at too many different parts, he can ONLY start or stop at the breakpoints settled.
Given a song that contain n parts that numbered from 1 to n, and the difficulty of every part (number of times
needed to practice). Now he has inserted k breakpoints on k different points between two adjacent parts of the song.
Then for each practice, he can start at the beginning or any of the breakpoints, and stop at the end
or any of the breakpoints. The time needed for each practice is exactly the number of parts practiced.
For example, if he started at part 3 and ended at part 7, then the time needed is (7-3+1) = 5.
You are to write a program that help SuBaRaSi to arrange his practice so that the total sum of his
practice time is minimum. In this way, he will thank you because he can then achieve his otaku's dream
more quickly.
Input
The input may contain many cases. In each case, the first line contain
two integers n, k (0<=k<n<=500) representing the number of parts in the song
and the number of breakpoints SuBaRaSi has set. In the following n lines, the i'th line
contain exactly one integer di (0<=di<=1000) denoting the difficulty of part i.
Then, in each of the following k lines contains an integer pi (1<=pi<n) representing the breakpoint
has been inserted between part pi and part pi+1. Note that these k integers are all distinct.
Output
For each case, print exactly one integer on a line representing the minimum time needed for SuBaRaSi to
become proficient in this song.
In the first case of the sample input, he can practice from beginning to the end once.
Then he practices part 2 to part 5 twice. Finally, he practices from part 2 to part 3 twice.
Therefore, the total time used is 18.