#include using namespace std; using ll = int64_t; constexpr ll INF = (1LL << 60) - 1; ll N; vector A, B; void input() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; A.resize(N), B.resize(N); for (ll i=0; i> A[i] >> B[i]; } void solve() { vector dp(N+1, -INF); dp[0] = 0; for (ll i=N-1; i>=0; --i) { for (ll j=N; j>0; --j) { dp[j] = max(dp[j] + A[i] * j, dp[j-1] + B[i]); } continue; } ll ans = 0; for (ll j=1; j<=N; ++j) ans = max(ans, dp[j]); cout << ans << "\n"; } int main() { input(); solve(); return 0; } /* 考察 後ろから考える dp[i][j] : i ターン目から始めて j 回攻撃するときの最大値 dp[i][j] = max(dp[i+1][j] + A[i] * j, dp[i+1][j-1] + B[i]) */