← 返回题单
题单练习 动态规划基础
← 上一题 下一题 →

A6953 | abc270D - Stones

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

问题陈述


高桥和青木将用序列 $(A_1, \ldots, A_K)$ 进行取子游戏。

有一堆最初包含 $N$ 的棋子。两位棋手将交替进行以下操作，高桥先下。

  • 选择与棋堆中当前棋子数相等的 $A_i$ 。从棋子堆中取出 $A_i$ 颗棋子。

    • 当棋子堆中没有棋子时，游戏结束。

    如果双方都试图在对局结束前最大限度地增加所取出的棋子总数，那么高桥将取出多少颗棋子？

    数据范围

  • $1 \leq N \leq 10^4$
  • $1 \leq K \leq 100$
  • $1 = A_1 A_2 \ldots A_K \leq N$
  • 输入值均为整数。

输入格式

输入内容由标准输入法提供，格式如下


$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_K$

输出格式

打印答案

输入输出样例

输入 #1
10 2
1 4
输出 #1
5
输入 #2
11 4
1 2 3 6
输出 #2
8
输入 #3
10000 10
1 2 4 8 16 32 64 128 256 512
输出 #3
5136
C++ 编辑器
输入
输出