You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Bessie 是一只变形虫，一开始它的体重是 $A$。在地板上从左往右依次放着 $N$ 块蛋糕， 第 $i$ 块蛋糕的重量是 $W_i$。变形虫从左边爬到右边，每次遇到一块蛋糕，如果蛋糕的重量恰好等于变形虫当前的重量，那么变形虫就吃掉这块蛋糕，吃完蛋糕后变形虫的重量增加了一倍；如果蛋糕的重量不等于变形虫当前的重量，那么变形虫永远也吃不了这块蛋糕了。变形虫只能从左往右爬，不能吃了某蛋糕后再往左爬。你的任务是计算变形虫的最终体重是多少。

输入格式

第一行，两个空格隔开的整数$A,N$，分别表示变形虫的体重和蛋糕的数目。

第二行，$N$ 个整数，空格分开，第 $i$ 个整数就是第 $i$ 块蛋糕的重量 $W_i$。

输出格式

一个整数，变形虫的最终体重。

样例

1 5
2 1 3 1 2

4

10 7
1 4 9 16 25 36 49

10

说明/提示

样例 1 解释

说明：变形虫首先会吃掉第 $2$ 块蛋糕， 体重变成 $2$。然后变形虫再吃掉第 $5$ 块蛋糕，体重变成 $4$。

样例 2 解释

说明：变形虫吃不了任何蛋糕，体重不变。

数据范围

$1 ≤ A ≤ 1000000000，1 ≤ N ≤ 200，1 ≤ W_i ≤ 1000000000$。