Rename buaa_team_select to buaa_team_select/City Metro

动态规划
A. City Metro
Time Limit: 1000msCase Time Limit: 1000msMemory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main
Submit
 
Status
 
PID: 29527
Font Size: 
+
 
-
In city L, a metro runs between two terminuses RG station and LF station. Every day, it runs m times for the direction from RG to LF. Now the transportation company asks you to design the timetable of them.
They provide you the metro's running time between each two neighboring stations. For each passenger who takes the metro of this direction, you are also provided her/his favorite departure station and when does she/he reach it. You can assume that the time of getting on and off the metro can be ignored.
You are told to minimize the sum of the passengers' waiting time. Please note that the timetable must ensure that every passenger can board the metro.
Input
The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.

For each test case:
The first line contains three integers: n, m and p (2 ≤ n ≤ 15, 1 ≤ m ≤ 50, 1 ≤ p ≤ 100). Here n is the number of stations (including the two terminuses); m is the times metro runs every day; and p is the number of passengers.
The second line contains (n-1) nonnegative integers, the i-th of them indicates the metro's running time between the i-th station and the (i+1)-th station. RG is the first station and the other stations are sequentially numbered. The sum of these integers is less than 500.
Then follows p lines, each of them contains two integers s and t (1 ≤ s ≤ n-1, 0 ≤ t ≤ 1 000), indicate a passenger’s departure station and the time she/he reaches it.
Output
For each test case, output only one integer in a single line -- the minimum sum of waiting time.
Sample Input
1
4 3 6
5 10 10
1 30
1 40
2 15
2 55
3 0
3 35
Sample Output
40