Alternating Sequence Game

There is an integer sequence of length n with elements a₁, a₂, …, a_n. Its alternating sum is defined as

$$S_0=a_1-a_2+a_3-\cdots,$$

Two players, Alice and Bob, play a game for k moves. They are given a list of k parameters: x₁, x₂, …, x_k. The moves are made in order: on the i-th move, the current player must choose an integer v from the range \(\{-x_i, -x_i+1, \dots, x_i-1, x_i\}\) and insert it at either the beginning or the end of the current sequence. Alice makes the first move (that is, when i is odd, Alice chooses the number; when i is even, Bob chooses).

After all moves, let the final sequence be \(a_1,a_2,\dots,a_{n+k}\). Its final score is computed as

$$S=\sum_{i=1}^{n+k}(-1)^{i-1}a_i.$$

Alice wants to maximize the final score, while Bob wants to minimize it. Assume both play optimally. Determine the final score.

Note: The initial alternating sum is computed from the given sequence as

$$S_0=a_1-a_2+a_3-\cdots.$$

A key observation is that inserting a number at the beginning or the end affects the alternating sum as follows:

• If a number \(v\) is inserted at the beginning, the new alternating sum becomes \(v - S\), where \(S\) is the sum before the move.
• If a number \(v\) is inserted at the end and the current sequence length is L (with parity p = L \bmod 2), the new alternating sum becomes \(S + (-1)^p \cdot v\).

Thus the move can be seen as a state transition:

• Front insertion: \(S' = v - S\).
• Back insertion: \(S' = S + (-1)^p \cdot v\).

Let f(i, S, p) be the final score given that there are k-i moves remaining, the current alternating sum is S, and the current parity is p (0 if even, 1 if odd). Then the recurrence is:

• If no moves remain (i.e. at the base level):
  \(f(k, S, p) = S\).
• If it is Alice's turn (maximizer) on move \(i\) with parameter \(x_i\):
  \(f(i, S, p) = \max\Big\{ \max_{v\in[-x_i,x_i]} f(i+1, v - S, 1-p), \; \max_{v\in[-x_i,x_i]} f(i+1, S + (-1)^p \cdot v, 1-p) \Big\}\).
• If it is Bob's turn (minimizer):
  \(f(i, S, p) = \min\Big\{ \min_{v\in[-x_i,x_i]} f(i+1, v - S, 1-p), \; \min_{v\in[-x_i,x_i]} f(i+1, S + (-1)^p \cdot v, 1-p) \Big\}\).

With careful observation and using the monotonicity of the functions involved, one can show that at each move the optimal choice is achieved by using one of the extreme values \(-x_i\) or \(x_i\). Hence the recurrence can be simplified as follows:

• Let the moves be indexed \(0 \ldots k-1\) (with \(x_0=x_1, x_1=x_2,\) etc.) and let the current parity be p (obtained from the initial length \(n\) as \(p=n\bmod2\)).
• If it is Alice's turn (when the move index is even):
  • Option 1 (front insertion): set \(v=x_i\) and update \(S' = x_i - S\).
  • Option 2 (back insertion): if \(p=0\), set \(v=x_i\) so that \(S' = S+x_i\); if \(p=1\), set \(v=-x_i\) so that \(S' = S-x_i\).
  • Then choose the maximum of these two outcomes.
• If it is Bob's turn (move index odd):
  • Option 1 (front insertion): set \(v=-x_i\) to get \(S' = -x_i - S\).
  • Option 2 (back insertion): if \(p=0\), set \(v=-x_i\) so that \(S' = S-x_i\); if \(p=1\), set \(v=x_i\) so that \(S' = S+x_i\).
  • Then choose the minimum of the two outcomes.

The initial state is given by the initial alternating sum \(S_0 = a_1-a_2+\cdots\) and parity \(p=n\bmod2\). The answer is then f(0, S0, p).

Input Format:

• The first line contains two integers n and k.
• The second line contains n integers representing the initial sequence.
• The third line contains k integers \(x_1, x_2, \dots, x_k\).

Output Format:

• Output a single integer, which is the final score after all moves have been played optimally.

Sample Explanation:

For example, consider the following test cases:

Test Case 1:

Input:
1 1
5
3
Output:
2

</p>

Explanation: The initial alternating sum is 5. Alice makes one move with \(x_1=3\). She can choose:

• Front: new score \(= 3 - 5 = -2\).
• Back: since the parity from a sequence of length 1 is 1, back insertion gives \(5 - 3=2\).

She picks the maximum, which is 2.

Test Case 2:

Input:
1 2
5
3 4
Output:
-6

</p>

Explanation: After Alice’s move, Bob can always respond to force the outcome to -6 when both play optimally.

Test Case 3:

Input:
2 3
3 1
2 5 1
Output:
6

</p>

Your task is to implement a program that computes the final score given the initial sequence and the sequence of moves.

inputFormat

The input consists of three lines:

• The first line contains two integers n and k (\(1 \le n, k \le 10^5\), though in practical cases the bounds may be smaller).
• The second line contains n integers representing the initial sequence.
• The third line contains k integers \(x_1, x_2, \dots, x_k\), where each \(x_i\) is positive.

You can assume that the numbers are such that the final answer fits in a 32-bit (or 64-bit) signed integer.

outputFormat

Output a single integer — the final score after performing all moves optimally.

sample

1 1
5
3

2