← 返回题目列表

AtCoder · icpc2013summer_warmingUp_j

J. 非常智力的卡牌游戏

中文机器翻译题面 查看原题

说明

Alice 和 Bob 决定使用一副牌玩新的纸牌游戏 N 卡。 N 是偶数。每张卡都有一个介于 -10^9 to 10^9.
鲍勃洗牌 M 次。在 i- 第一次,他交换了 [1, k_i)第张牌和 [k_i, n]从牌堆顶部数起的第张牌。
例如,当牌组为 <1, 2, 3, 4, 5, 6> 和 k_i 等于 4,牌组变为 <4, 5, 6, 1, 2, 3> 洗牌后。
当然,Alice 可以在任意次数后停止他的洗牌 0 次也。 (她停止洗牌后,他不再洗牌。)
当她停止洗牌或他结束洗牌 M 次时,爱丽丝获得牌堆的上半部分。她拿到的牌的总和什么时候达到最大?

输入

输入文件的第一行包含 N 和 M (2 \leq N \leq 10^5, 1 \leq M \leq 10^5),这是纸牌和洗牌的数量。 N 是偶数。
第二行包含 N 从牌堆顶部开始写在牌上的整数。整数介于 -10^9 和 10^9 包括在内。
第三行包含 M 整数 \{k_i\} (2 \leq k_i \leq N).

输出

输出Alice可以获得的最大牌数。

示例输入

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

示例输出

2