商品券を無視
端数の扱いが面倒なので，まずは商品券を無視して考える． \(u-p \geq 0\) なら買う， そうで無ければ買わない， が最善．
商品券を考慮
端数の扱いを綺麗に扱うのは難しそう． そこで，全探索したいので，DPが良さそう． DPを考えるにあたって，同一視できる物や区別しないといけない物を考える．
- 端数は区別する必要があるので，記録しながら遷移．
- 今調べている番号 \(i\) 以前は，どれを買ったかは区別しなくてよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll dp(100, -INFL);
dp[0] = 0; // init: 端数0以外はありえないケース
rep(i,n){
ll p, u; cin >> p >> u;
vll old(100, -INFL); // rem : -INFL
swap(dp, old);
rep(x,100){
ll y = (p+x)%100;
ll r = ((p+x)/100)*20;
chmax(dp[y], old[x] + u - p + r);
chmax(dp[x], old[x]);
}
}
ll ans = -INFL;
rep(x,100){
chmax(ans, dp[x]);
}
assert(ans > -INFL);
cout << ans << endl;
return 0;
}
