就是01分数规划的思路，只不过当把w[i]-r*t[i]>0的选完以后如果w值还没达到要求，那就再01背包dp一下就好了（dp时w值>W的时候就存在W里就不会爆内存了）。
（跑得很慢..大概是二分的姿势有问题...）
（貌似还有直接dp的做法？不会）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<ctime>
#define pa pair<double,int>
#define LL long long
using namespace std;
const int maxn=,maxm=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,W,w[maxn],t[maxn];double f[maxn][maxm];
pa x[maxn]; bool judge(double r){
for(int i=;i<=N;i++) x[i]=make_pair(t[i]-r*w[i],i);
sort(x+,x+N+);
int sw=,mm=N;double sr=,mr=-;
for(int i=N;i&&x[i].first>=;mm=--i){
sw+=w[x[i].second];sr+=x[i].first;
}
if(sw>=W) return ; f[][]=;for(int j=;j<=W-sw;j++) f[][j]=-;
for(int i=;i<mm;i++){
for(int j=;j<=W-sw;j++) f[i+][j]=f[i][j];
for(int j=;j<W-sw;j++){
f[i+][min(W-sw,j+w[x[i+].second])]=\
max(f[i+][min(W-sw,j+w[x[i+].second])],f[i][j]+x[i+].first);
}
}
for(int i=;i<=mm;i++) mr=max(mr,f[i][W-sw]);
return mr+sr>=;
} int main(){
int i,j,k;
N=rd(),W=rd();
for(i=,j=;i<=N;i++) w[i]=rd(),t[i]=rd();
double l=,r=2.5e7;
while(r-l>1e-){
double m=(l+r)/;
if(judge(m)) l=m;
else r=m-1e-;
}printf("%d\n",(int)(l*));
return ;
}