~~这种题都能撞到我也是醉了(貌似楼上有位写了我这个做法)~~
考虑暴力,一个数不会算入答案,当且仅当它比$m$大(肯定可以减少它本身这个集合),或者是不考虑它,有其他的值可以和他凑成$\ge m$的数
于是我们可以背包,对于每一个数,把他忽略做一遍$01$背包,然后检查$[m - a[i], m)$是否可以凑成即可
发现任意两个点的背包有很多重复信息,于是我们考虑分治。
分治中每一个节点存储的是**不**包括这个节点所代表的点的$dp$数组,然后每一次分治的时候$[l, mid]$对$[mid + 1, r]$这个节点的贡献加进去,$[mid + 1, r]$对$[l, mid]$这个结点的贡献加进去即可(不理解可以参考代码)
这样复杂度是$O(NMlogN)$的,你可以使用$bitset$优化,但是本题数据叫水,不需要$bitset$也是可以的
### $\rm Code:$
```cpp
/* This code is written by Nemlit */
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define rep(i, a, b) for(re int i = (a); i <= (b); ++ i)
#define drep(i, a, b) for(re int i = (b); i >= (a); -- i)
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define maxn 5005
int n, m, ans, dp[maxn][maxn], a[maxn], d[maxn];
long long sum;
il void solve(int l, int r, int *Dp) {
if(l == r) {
rep(i, 0, m) dp[l][i] = Dp[i];
return;
}
int DP[m + 5], mid = (l + r) >> 1;
memcpy(DP, Dp, sizeof(DP));
rep(i, l, mid) drep(j, a[i], m) DP[j] |= DP[j - a[i]];
rep(i, mid + 1, r) drep(j, a[i], m) Dp[j] |= Dp[j - a[i]];
solve(l, mid, Dp), solve(mid + 1, r, DP);
}
signed main() {
n = read(), m = read(), d[0] = 1;
rep(i, 1, n) a[i] = read(), sum += a[i], ans += a[i] >= m;
solve(1, n, d);
if(sum >= m) rep(i, 1, n) if(a[i] < m) rep(j, m - a[i], m - 1) if(dp[i][j]) { ++ ans; break; }
printf("%lld", n - ans);
return 0;
}
```