Obviously, it is optimal to put out each candle immediately when he visits there. Also, the duration of \(10^{100}\) minutes is long enough to assume that he visits all the coordinates that candles is placed at (including those which he visits after they burn out). Moreover, once the order of visiting candles is determined, it is optimal to head to the next candle straight on the shortest path at the full speed. Therefore, we can assume that he moves at the speed \(1\), and he changes his direction only at where a candle is.

Additionally, for simplicity we assume that there is a candle at coordinate \(0\) of length \(0\) at time \(0\), which does not change the answer. Note that from now on the value \(N\) is incremented by one than the original value. Now let \(X_1<X_2<\cdots <X_N\) be the positions of the candles, then when Takahashi visits \(X_i\) for the first time, the range that Takahashi has visited so far is represented as \([X_i,X_j]\) or \([X_j,X_i]\), and the next candle to visit is either \(X_{i-1}\) or \(X_{j+1}\) (if exists, respectively) for the former case, or \(X_{j-1}\) or \(X_{i+1}\) for the latter case. We can also see that the last candle to visit is \(X_1\) or \(X_L\).

Next, let us modify the problem setup a little bit. Specifically, we apply such amendments that

• a candle does not burn out, and can have a negative length.
• Before he starts moving, he can remove some candles. (Removed candles do not affect the final sum of lengths at all)

Then the answer under these assumptions is same to that of the original. This is because, while these modifications do not obviously increase the answer, the value achieved in the original problem can be obtained by the action of “removing those candles beforehand that would burn out by the time he reaches them if he acts optimally to maximize the answer.” [](Hereinafter we assume that the candles will remain burning until he put them out (with negative lengths)).

Now that candles will never burn out as time passes, the sum of candles’ lengths decreases every minute by \(N-(\text{Number of candles removed firsthand})-(\text{Number of canldes he put out so far})\). Focusing on this “remaining number”, we can rephrase the problem as follows.

• Takahashi initially stands at coordinate \(0\) with a counter, and the score is \(0\).
• The value of counter \(C\) can be initialized to any integer from \(0\) through \(N\), inclusive.
• Value \(H_i\) is associated with coordinate \(X_i\).
• Takahashi can change his position to increase or decrease his coordinate by \(1\). Every time he moves by \(\pm 1\), the score decreases by \(C\). (It can be negative.)
• Every time he visits coordinate \(X_i\) for the first time, if the counter has value \(C > 0\), he can choose whether he decrements the counter by \(1\) and add \(H_i\) to the score.
• Maximize the final score.

This problem can be solved with the following Dynamic Programming (DP).
Let \(dp[i][j][flag][k]\) be the maximum score that can be obtained from now on, if he has visited the range \([X_i,X_j]\) so far and is currently at (the left end \(X_i\) if \(flag=0\), or the right end \(X_j\) if \(flag=1\)), and if the value of counter after his choice for his current coordinate has determined. (In other words, if the current score is \(s\), the maximum final score obtained if he acts optimally can be written as \(s+k\), where \(k\) is a constant independent of \(s\); this \(k\) is the value of the DP.)
Here, \(1\leqq i\leqq j\leqq N\), \(flag=0\) or \(1\), and \(0\leqq k \leqq N-(j-i+1)\)

The initial value is \(dp[1][N][flag][0]=0\), and the desired answer is \(\displaystyle\max_{0\leq k\leq N-1} dp[i_0][i_0][flag][k]\), where \(i_0\) satisfies \(X_{i_0}=0\). (We do not have to care \(k=N\), because there is a candle of height \(0\).) As for transition, we can obtain \(dp[i][j][flag][k]\) from the values of \(dp[i-1][j][flag][k-1]\), \(dp[i-1][j][flag][k]\), \(dp[i][j+1][flag][k-1]\), and \(dp[i][j+1][flag][k]\), in an \(O(1)\) time, so the transitions cost a total of \(O(N^3)\) time, which is fast enough.

Therefore, the problem has been solved.

Sample code in c++:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N (ll)302
#define INF (ll)4000000000000000001
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
#define all(c) (c).begin(), (c).end()


int main(void) {
	ll n, x, y, d;
	vector<pair<ll, ll> >c;
	ll dp[N][2][N];
	ll dp2[N][2][N];
	ll i0;
	ll ans = 0;
	cin >> n;
	d = 0;
	rep(i, n) {
		cin >> x >> y;
		if (x == 0) {
			d++;
			ans += y;
		}
		else c.pb({ x,y });
	}
	n = n + 1 - d;
	c.pb({ 0,0 });
	sort(all(c));
	rep(i, n) {
		if (c[i].second == 0)i0 = i;
	}
	rep(i, N) {
		rep(ii, 2) {
			rep(j, N) {
				dp[i][ii][j] = -INF;
				dp2[i][ii][j] = -INF;
			}
			dp[i][ii][0] = 0;
		}
	}
	rep3(j, n - 2, 0) {
		rep(i, n - j) {
			rep2(k, 1, n - j - 1) {
				if (i > 0) {
					dp2[i][0][k] = max(dp2[i][0][k], dp[i - 1][0][k] - (k*(c[i].first - c[i - 1].first)));
					dp2[i][0][k] = max(dp2[i][0][k], dp[i - 1][0][k - 1] + c[i - 1].second - (k*(c[i].first - c[i - 1].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i - 1][0][k] - (k*(c[i + j].first - c[i - 1].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i - 1][0][k - 1] + c[i - 1].second - (k*(c[i + j].first - c[i - 1].first)));
				}
				if ((i + j) < (n - 1)) {
					dp2[i][0][k] = max(dp2[i][0][k], dp[i][1][k] - (k*(c[i + j + 1].first - c[i].first)));
					dp2[i][0][k] = max(dp2[i][0][k], dp[i][1][k - 1] + c[i + j + 1].second - (k*(c[i + j + 1].first - c[i].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i][1][k] - (k*(c[i + j + 1].first - c[i + j].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i][1][k - 1] + c[i + j + 1].second - (k*(c[i + j + 1].first - c[i + j].first)));
				}
			}
		}
		rep(i, n - j) {
			rep2(k, 1, n - j - 1) {
				rep(ii, 2) {
					dp[i][ii][k] = dp2[i][ii][k];
					dp2[i][ii][k] = -INF;
				}
			}
		}
	}

	x = 0;
	rep(k, n) {
		x = max(x, dp[i0][0][k]);
		x = max(x, dp[i0][1][k]);
	}
	ans += x;
	cout << ans << endl;

	return 0;
}