DPをしたいが，順序によって得られる値が変わる． よって，最適な順序にソートしてからDPする．
\(i \rightarrow j\) , \(j \rightarrow i\) のそれぞれに対して得点を調べて， 差分を計算すれば \( a_{i}/ b_{i} \geq a_{j} / b_{j}\) の順で行うのが最善と分かる． これは直観にも合致する． 気持ちとしては \(a_{i}\) を大きい順に， \(b_{i}\) は小さい順に行いたいから．
最適順でソートしてからDPというのは， 一般的な話として使える．
例えば，食塩水のDPも最適順にソートしている． また，順によらないDPは，最適解の一つとして初期の並びを使えるということなので， やはりソートDPの形に帰着される．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,h;
cin >> n >> h;
vll a(n), b(n);
rep(i,n) cin >> a[i] >> b[i];
rep(i,n) v[i] = {a[i], b[i]};
sort(all(v), [&](pll x, pll y){
return x.first * y.second > x.second * y.first; // rem : >= だと RE
});
vll dp(2e5+10, -INFL);
ll c = 1e5+5;
dp[h+c] = 0;
rep(i,n){
rep(x,h+1){
auto [s,t] = v[i];
chmax(dp[x-t+c], dp[x+c] + s*x);
}
}
ll ans = -INFL;
for(auto val:dp){
chmax(ans, val);
}
cout << ans << endl;
return 0;
}
