J - Very Intellectual Card Game
Editorial
/ 
Alice and Bob decide to play a new card game using a deck with 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?
The first line of the input file contains 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 the maximal sum of the cards that Alice can get.
/ 
Time Limit: 1.5 sec / Memory Limit: 93 MB
Description
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
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