AT_icpc2013summer_warmingUp_j Very Intellectual Card Game

[problemUrl]: https://atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_j 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 $ and\ k_i $ equals $ 4 $, the deck becomes $ 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. ``` 10 5 1 -3 2 2 -4 1 1 5 -2 -2 2 8 5 8 10 ``` ``` 2 ```

N/A

N/A