ll@n,@w,d[w+1]{},r[w],b;
rep(n){
	ll@x,@v;
	rrep(i,x,w+1){
		d[i]>?=d[i-x]+v;
	}
}
b=d[w];
rrep(i,1,w+1){
	b>?=d[w-i];
	r[i-1]=b-d[w-i]+1;
}
wtLn(r(w));