J - Very Intellectual Card Game
Editorial
/

Alice and Bob decide to play a new card game using a deck with

Bob shuffles the deck

For example, when the deck is

Alice can stop his shuffle after arbitrary times, of course

When she stops shuffle or he ends shuffle M times, Alice gets the upper half of the deck. When does the sum of the cards she gets become maximum?

The first line of the input file contains

The second line contains

The third line contains

Output the maximal sum of the cards that Alice can get.

Time Limit: 1.5 sec / Memory Limit: 93 MB

### Description

`N`cards.

`N`is even. Each card has a number between

`-10^9`to

`10^9`.

Bob shuffles the deck

`M`times. In the

`i`-th time, he swaps the

`[1, k_i)`-th cards and

`[k_i, n]`-th cards counting from the top of the deck.

For example, when the deck is

`<1, 2, 3, 4, 5, 6>`and

`k_i`equals

`4`, the deck becomes

`<4, 5, 6, 1, 2, 3>`after shuffle.

Alice can stop his shuffle after arbitrary times, of course

`0`times also. (He does not shuffle after she stopped his shuffle.)

When she stops shuffle or he ends shuffle M times, Alice gets the upper half of the deck. When does the sum of the cards she gets become maximum?

### Input

`N`and

`M`(

`2 \leq N \leq 10^5`,

`1 \leq M \leq 10^5`), which is the number of cards and shuffles.

`N`is even.

The second line contains

`N`integers that are written on the cards from the top of the deck. The integers are between

`-10^9`and

`10^9`inclusive.

The third line contains

`M`integers

`\{k_i\}`(

`2 \leq k_i \leq N`).

### Output

### Sample Input

10 5 1 -3 2 2 -4 1 1 5 -2 -2 2 8 5 8 10

### Sample Output

2