P8002 Alice and Bob are playing a Normal Game

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.

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 one integer in one line, representing the answer.

**This problem uses bundled testdata.** | Subtask ID | Score | Special Constraints | | :----------: | :----------: | :----------: | | $0$ | $25$ | $n,k,x_i\le 5$ | | $1$ | $25$ | $n,k\le 10$ | | $2$ | $25$ | $n,k\le 100$ | | $3$ | $25$ | No special constraints | 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