题解

这题是相当经典的动态规划了，类似于 01 背包问题。

定义 $dp[i][j]$ 为，考虑前 $i$ 个帖子，点赞数为 $i$ 所需的最少帖子数。

用 $cur[i]$ 表示当前帖子能造成的点赞数。

状态转移为：$dp[i]j] = min(dp[i - 1][j - cur[i] + 1, d[i][j])$

题目描述

小红有n个账号，每个账号粉丝数为$a_i$。

这天他又创建了一个新账号，他希望新账号的粉丝数恰好等于$x$。为此他可以向自己已有账号的粉丝们推荐自己的新账号，这样以来新账号就得到了之前粉丝的关注。

他想知道，他最少需要在几个旧账号发“推荐新账号”的文章，可以使得他的新账号粉丝数恰好为$x$，除此以外，他可以最多从中选择一个账号多次发“推荐新账号”的文章。

假设一个旧账号粉丝数为$a_i$，如果仅推荐一次，那么新账号粉丝数增加$\lfloor{\frac{a_i}{2}}\rfloor$，如果多以推荐，则粉丝数增加$a_i$

输入描述

输入包含2行。

第一行两个正整数$n,x(1≤n,x≤100)$，分别表示小红的旧账号个数，和新账号想要的粉丝数。

第二行$n$个正整数$a_i(1≤a_i≤100)$，表示小红每个旧账号的粉丝数。

输出描述

输出包含一行一个整数，表示小红最少需要向多少个旧帐号推荐新账号，如果无法做到，输出-1。

样例

输入

5 8
1 2 3 4 10

输出

2