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.

T3 蛋糕（cake）

题目描述

小 C 过生日了，他买了 $m$ 块蛋糕，第 $i$ 块蛋糕的大小为 $a_i$。

小 C 喜欢 $2$ 这个数，所以他买的所有蛋糕的大小一定是 $2$ 的整数幂，即 $\forall 1\le i\le m,\exists 0\le k$，$a_i=2^k$。

小 C 可以用一把刀切蛋糕（切的蛋糕大小必须大于 $1$），他可以将一块大小为 $x$ 的蛋糕一分为二切成两块大小为 $\frac{x}{2}$ 的蛋糕。

小 C 想要选出一些蛋糕送给朋友，但小 C 有强迫症，他想让选出蛋糕的大小之和为 $n$。

由于切蛋糕是需要体力的，小 C 想要知道最少需要切多少次蛋糕使得他能够选出一些蛋糕使得选出蛋糕的大小之和为 $n$。

如果怎样切蛋糕都无法选出一些蛋糕使得选出蛋糕的大小之和为 $n$，请告诉小 C 不可能（即输出 -1）。

输入格式

第一行输入两个数字 $n,m$，分别表示选出蛋糕的大小之和，最初蛋糕的块数。

第二行输入 $m$ 个整数，第 $i$ 个整数表示第 $i$ 块蛋糕的大小 $a_i$。

输出格式

共一行，输出一个整数，表示切蛋糕的最小次数，若不可能输出 -1。

样例 1 输入

10 3
1 1 32

样例 1 输出

2

样例 1 解释

• 选择大小为 $32$ 的蛋糕切一刀，变成两块大小为 $16$ 的蛋糕。
• 选择大小为 $16$ 的蛋糕切一刀，变成两块大小为 $8$ 的蛋糕。

可以选出大小分别为 $1,1,8$ 的蛋糕，使得大小之和为 $10$，故最小次数为 $2$。

样例 2 输入

20 5
1 1 2 8 16

样例 2 输出

0

其余样例见下发文件。

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n \le 256$，$m\le 4$，$1\le a_i\le 512$。
• 对于 $40\%$ 的数据，保证 $n \le 4096$。
• 对于另 $20\%$ 的数据，保证 $m=1$。
• 对于另 $20\%$ 的数据，保证 $m=2$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^{18}$，$1\le m\le 10^5$，$1\le a_i\le 10^{13}$。