#XSDCSPJ25044. 王老师的蛋糕

王老师的蛋糕

题目描述

王老师过生日了,他买了 m 块蛋糕,第 i 块蛋糕的大小为 aia_i

王老师喜欢 2 这个数,所以他买的所有蛋糕的大小一定是 2 的整数幂,即 1im,0kai=2k∀1≤i≤m,∃0≤k,a_i​ =2^k

王老师可以用一把刀切蛋糕(切的蛋糕大小必须大于 1),他可以将一块大小为 x 的蛋糕一分为二切成两块大小为 x​/2 的蛋糕。

王老师想要选出一些蛋糕送给朋友,但王老师有强迫症,他想让选出蛋糕的大小之和为 n。

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

如果怎样切蛋糕都无法选出一些蛋糕使得选出蛋糕的大小之和为 n,请告诉王老师不可能(即输出 -1)。

输入格式

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

第二行输入 m 个整数,第 i 个整数表示第 i 块蛋糕的大小 aia_i

输出格式

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

样例输入 1

10 3
1 1 32

样例输出 1

2

样例输入 2

20 5
1 1 2 8 16

样例输出 2

0

提示/说明

样例 1 解释

选择大小为 32 的蛋糕切一刀,变成两块大小为 16 的蛋糕。 选择大小为 16 的蛋糕切一刀,变成两块大小为 8 的蛋糕。 可以选出大小分别为 1,1,8 的蛋糕,使得大小之和为 10,故最小次数为 2。

数据范围

对于 20% 的数据,保证 n256m41ai512n≤256,m≤4,1≤a_i ≤512。 对于 40% 的数据,保证 n4096n≤4096。 对于另 20% 的数据,保证 m=1m=1。 对于另 20% 的数据,保证 m=2m=2。 对于 100% 的数据,保证 1n10181m1051ai10131≤n≤10^18 ,1≤m≤10^5 ,1≤a i​ ≤10^13