题目描述
小蓝正在上一节数学课,老师在黑板上给出了一个整数,接下来老师又给出了一些整数,老师问是否可以从后面所给定的整数中选取一些让它们的和等于第一次给的整数。小蓝觉得这个问题太简单了,于是他问你,给定一个目标整数 xxx , 接下来是依次给出的 nnn 个整数,第 iii 个整数 aia_iai。从前往后依次选则给定的整数 , 对于一个数要么加上它要么忽略它,在某一位置可以让当前所选取数的和除以 222 ,如果当前结果是负数向上取整,如果是正数就向下取整,后继续之前操作,你只有一次机会除以 222 。最少需要选多少个数,使其最终的结果等于目标整数,当然你可以一个都不选取,这样你最后的结果就是 000 。
形式上:
首先给出一个目标数 xxx 。接下来给出 nnn 个整数,你可以从中选取 kkk 个 , ap1,ap2,ap3...apk(pi<pj,i<j)a_{p_1},a_{p_2},a_{p_3}...a_{pk} (p_i < p_j , i < j)ap1,ap2,ap3...apk(pi<pj,i<j),并且使 ∑j=1kaj=x\sum_{j=1}^{k}{a_j} = x∑j=1kaj=x , 或者 ∑j=1saj÷2+∑j=s+1kaj=x\sum_{j=1}^{s}{a_j} \div 2 +\sum_{j=s+1}^{k}{a_j} =x∑j=1saj÷2+∑j=s+1kaj=x (1≤s≤k)(1 \le s \le k)(1≤s≤k) ,此道题目中,如果除以 222 的数大于 000 , 向下取整,小于 000 向上取整。
输出最少选取多少个数使选取的数经上述操作结果等于目标值,如果无论怎么选都不能构成目标值,输出 −1-1−1 。
输入
第一行一个整数 n,xn,xn,x (1≤n≤300,−104≤x≤104)(1 \leq n \le 300, -10^4 \le x \le 10^4)(1≤n≤300,−104≤x≤104) 。
第二行 nnn 个整数数,代表 aia_iai , (−100≤ai≤100)(-100 \le a_i \le100)(−100≤ai≤100)。
输出
一行一个整数,表明结果。
样例输入 Copy
1 0
100
样例输出 Copy
0
提示
目标值为 00 ,所以不需要选择任何数就可以等于目标值