题目描述

$alice$ 和 $bob$ 在玩一个取石子的游戏。

刚开始，有 $N$ 个石子，还有一个长度为 $K$ 的序列 $A = \{A_1,A_2,\cdots,A_K\}$。

现在，他们要按照以下规则轮流取石子：

• 对于每次操作，他可以选择一个 $i$（$1 \leq i \leq K$），这时他会取走 $A_i$ 块石子。

• 当一个人没法取石子时，游戏结束。

现在，$alice$ 先取石子，$bob$ 后取石子。他们都想尽可能的最大化他们自己取走的石子数量。

若他们都以最优策略取石子，最后 $alice$ 会取走多少块石子？

输入格式

第一行两个正整数 $N, K$

第二行有 $K$ 个正整数，其中第 $i$ 个表示 $A_i$

输出格式

一行一个正整数，表示若他们都以最优策略取石子，最后 $alice$ 取走的石子数量。

样例 #1

样例输入 #1

10 2
1 4

样例输出 #1

5

• alice 拿走4个
• bob 拿走4个
• alice 拿走1个
• bob 拿走1个

在这个例子里， alice 最多拿走了5个

样例 #2

样例输入 #2

11 4
1 2 3 6

样例输出 #2

8

样例 #3

样例输入 #3

10000 10
1 2 4 8 16 32 64 128 256 512

样例输出 #3

5136

提示

• $1\ \leq\ N\ \leq\ 10^4$
• $1\ \leq\ K\ \leq\ 100$
• $1\ =\ A_1\ <\ A_2\ <\ \ldots\ <\ A_K\ \leq\ N$
• 所有数据都是整数

大样例下载