体现了出题人灭尽毒瘤的远大志向。
首先枚举最小的无法放入的物品 \(i\)，较其更小的物品肯定已经全部被放进去了，且有至少一个该物品没有被放进去。
于是我们枚举 \(i\)，对于比 \(i\) 大的物品随便跑一个背包算一下对于每个已占用大小的可行性，然后再对物品 \(i\) 跑可行性（注意数量要减 \(1\)，留出一个放不进去），然后枚举一下使最后一个放不进去的大小的总方案数即可。
但是我们显然不想做 \(n\) 次背包，于是我们从大到小枚举 \(i\)，每次做背包都继承上一次的数据。
然后没了。\(\mathrm O(nm)\)。
#include <bits/stdc++.h>
#define llong long long
#define N 505
#define M 100005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}constexpr int p = 19260817;struct Item{int w, c;
};
Item a[N];int n, m, ans;
int prew[N];
int dp[2][M];int main(){read(n, m);for(int i = 1; i <= n; ++i) read(a[i].c, a[i].w);sort(a+1, a+n+1, [&](Item o1, Item o2){return o1.w<o2.w;});for(int i = 1; i <= n; ++i) prew[i] = prew[i-1]+a[i].w*a[i].c;if(prew[n] <= m) ++ans;dp[n&1^1][0] = 1;for(int i = n; i >= 1; --i){int rt = i&1, lt = i&1^1;--a[i].c;for(int j = 0; j < a[i].w; ++j){int now = 0;for(int k = 0; a[i].w*k+j <= m; ++k){now = (now+dp[lt][k*a[i].w+j])%p;dp[rt][k*a[i].w+j] = now;if(k >= a[i].c) now = (now-dp[lt][(k-a[i].c)*a[i].w+j]+p)%p;}}for(int j = m-prew[i-1]; j > max(m-prew[i-1]-a[i].w, -1); --j){ans = (ans+dp[rt][j])%p;}for(int j = m; j >= (a[i].c+1)*a[i].w; --j)dp[rt][j] = (dp[rt][j]+dp[lt][j-(a[i].c+1)*a[i].w])%p;}printf("%d", ans);return 0;
}