完了我连背包都不会了……
考虑暴力，先枚举最小的数是哪个，设大小为$d_i$，个数为$k_i$，所有比它小的数的总和是$sum$，然后把所有比它小的全都装进背包，它以及比他大的做一个多重背包，那么设$dp[j]$表示在剩下的这些数里取的总和为$j$时的方案数，那么$$ans+=sum_{j=m-sum-d_i+1}^{m-sum} dp[j]$$
上面的式子意思就是，将所有比它小的全放进去之后，枚举背包剩余的空间，统计所有方案数。因为不能让把任何大于等于它的在统计之前就放进去，所以下界是$m-sum-d_i+1$
然后现在的问题就是怎么统计了才能过。我们可以从大到小枚举，这样的话每做到一个物品就只需要对它自己做多重背包，不需要重新dp了
接下来的操作真的是学到了……在做多重背包的时候把$j$按照模$d_i$的取值分为不同的组，然后时间复杂度就能优化到$O(nm)$
简单来讲的话，就是转移的时候$dp[j]+=dp[j-d_i]+dp[j-d_i*2]...+dp[j-d_i*k_i]$，发现每一个$j$只会被与它模$d_i$同余的转移到，于是我们枚举这一个余数，统计与它同余的数的前缀和，然后从小到大转移并不断维护前缀和即可（真的很妙）
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=505,M=1e5+5,mod=19260817; 19 struct node{ 20 int k,d; 21 inline bool operator <(const node &b)const{return d<b.d;} 22 }a[N]; 23 int n,m,ans,tot,dp[2][M],t; 24 inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;} 25 inline int del(int x,int y){return x-y<0?x-y+mod:x-y;} 26 void ins(int k,int w){ 27 int sum,H; 28 for(int d=0;d<=w-1;++d){ 29 H=sum=0; 30 for(int j=0;j<=(m-d)/w;++j){ 31 sum=add(sum,dp[t^1][j*w+d]); 32 if(H<j-k) sum=del(sum,dp[t^1][(H++)*w+d]); 33 dp[t][j*w+d]=sum; 34 } 35 } 36 } 37 int main(){ 38 // freopen("testdata.in","r",stdin); 39 n=read(),m=read(); 40 for(int i=1;i<=n;++i) a[i].k=read(),a[i].d=read(),tot+=a[i].k*a[i].d; 41 if(tot<=m) return puts("1"),0; 42 sort(a+1,a+1+n); 43 dp[0][0]=1; 44 for(int i=n;i;--i){ 45 tot-=a[i].k*a[i].d,t^=1; 46 ins(a[i].k-1,a[i].d); 47 for(int j=max(m-tot-a[i].d+1,0);j<=m-tot;++j) ans=add(ans,dp[t][j]); 48 ins(a[i].k,a[i].d); 49 } 50 printf("%d ",ans); 51 return 0; 52 }