Problem Description

Given a sequence of length $n$, Alice and Bob take turns performing a total of $k$ operations. In the $i$-th operation, the current player must choose an integer in $-x_i \sim x_i$ and insert it at the beginning or the end of the sequence. Alice moves first (that is, when $i$ is odd, Alice inserts an integer in $-x_i \sim x_i$; when $i$ is even, Bob inserts an integer in $-x_i \sim x_i$).

Let the final sequence be $a_1,a_2,\dots,a_{n+k}$. The score is $\sum_{i=1}^{n+k} (-1)^{i-1}a_i$. Alice wants to maximize the score, and Bob wants to minimize it. When both players use optimal strategies, find the final score.

Input Format

The first line contains two positive integers $n,k$, representing the initial sequence length and the number of operations.

The next line contains $n$ integers $a_1,a_2,\dots,a_n$, representing the initial sequence.

The next line contains $k$ non-negative integers, where the $i$-th number is $x_i$.

Output Format

Output one integer in one line, representing the answer.

2 2
1 3
2 2

-2

Hint

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le n,k\le 2\times 10^5$ and $0\le |a_i|,x_i\le 10^9$.

This problem has many test points. To ensure judging speed, the time limit is 500 ms, and it is guaranteed to be more than 5 times the maximum time used by the standard solution.

Translated by ChatGPT 5