#include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(i=0; i=a; --i) #define in(a) cin >> a #define out(a,b) cout << a << b #define print_vec(v) for(auto it=v.begin();it!=v.end();++it)cout<<*it <<" ";cout< &v, vector &d, int j, int si, int ai, int m){ if(d[j]==0) return; if(j+si>m) return; if(v[j]) return; if(d[j+si]>d[j]+ai) return; else{ func(v, d, j+si, si, ai, m); d[j+si]=d[j]+ai; v[j+si]=true; } return; } int main(void){ int i, j; lint k, cnt=0, x, y; lint p, q, n, m; string s; in(n);in(m); vector > v(n); rep(i,n){ lint a, b; in(a);in(b); v[i]=make_pair(a, b); } vector d(m+1, 0); rep(i, n){ // print_vec(d); lint si, ai; tie(si, ai) = v[i]; if(si<=m){ vector f(m+1, false); if(d[si]