Japan Alumni Group Summer Camp 2013 Warming Up

J - Very Intellectual Card Game


Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB

Description

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?

Input

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

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

Sample Input

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

Sample Output

2

Source name

The First KMCMonthly Contest

Submit提出する