Interval Game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef and his brother Chefu are playing a game. The game consist of two sequences of integers A of length N and B of length M, and it will last for exactly M turns, Chef will play in odd turns whereas Chefu will play in even turns (turns and sequences are 1based).
In the ith turn, the corresponding player should select an interval (continuous subsegment) of sequence A of length B_{i} that is strictly inside the interval selected in previous turn, i.e. if the interval in previous turn was [l,r] then if the interval in current turn is [u,v] then it should satisfy l < u ≤ v < r, except in the first turn where the player can select any interval of length B_{1}.
Initially the score of the game is 0. If it was Chef's turn then we add to the score of the game points equal to sum of integers of the selected interval of sequence A. If it was Chefu's turn then we subtract from the score of the game points equal to sum of integers of the selected interval of sequence A.
Chef wants to maximize the score of the game in the end while Chefu want to minimize it. Can you find out the score of the game in the end given that both Chef and Chefu are playing optimally.
Input
The first line contains an integer T denoting the number of testcases. Description of T test cases follow.
First line of each test case contains two space separated integers N and M, denoting the length of the sequence and the number of turns for which the game will last, respectively.
Second line of each test case contains N space separated integers denoting the sequence A
Third line of each test case contains M space separated integers denoting the sequence B
Output
For each test case, output a single integer in a separate line corresponding to the score of the game at the end of the game.
Constraints
 1 ≤ T ≤ 10,000
 1 ≤ sum of N in all testcases ≤ 300,000
 1 ≤ A_{i} ≤ 1,000,000,000
 1 ≤ M ≤ 200
 1 ≤ B_{i} ≤ N
 For each valid i: B_{i+1} + 2 ≤ B_{i}
Subtasks
 Subtask #1 (20 points): sum of N in all testcases ≤ 400
 Subtask #2 (20 points): M = 2
 Subtask #3 (60 points: No additional constraints
Example
Input: 1 8 3 3 7 5 4 9 6 1 3 6 3 1 Output: 20
Explanation
Example case 1. Chef chooses the interval [1, 6] (i.e. (3, 7, 5, 4, 9, 6)). The score now is 34 points.
In the next turn, Chefu chooses the interval [3, 5] (i.e. (5, 4, 9)). The score now is 34  18 = 16 points.
In the next turn, Chef chooses the interval [4, 4] (i.e. (4)). So finally score of the game is 16 + 4 =20.
This is the score of the game when both Chef and Chefu play optimally.
Author:  kingofnumbers 
Tester:  mgch 
Tags  kingofnumbers 
Date Added:  8062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 