You have two arrays of integers, $V=\{V_1,V_2,\ldots,V_N\}$ and $P=\{P_1,P_2,\ldots,P_N\}$, where both have $N$ number of elements. Consider the following function:

score = 0

int Go(step, energy) {
    if (step == N) {
        score += V[step];
        return (score);
    }
    else {
        int way = random(1, 2);
        if (way == 1) {
            score += V[step];
        }
        else {
            energy = P[step];
        }
        if (energy > 0) {
            Go(step + 1, energy - 1);
        }
        else {
            KillTheWorld();
        }
    }
}

What is the maximum possible value of score that we can get in the end, if we call $Go(1,0)$?. 

Note that the function should never invoke KillTheWorld function. And $\textit{random(1,2)}$ generates a random integer from set  [1, 2]. 

It is guaranteed there will be a solution that wont kill the world.

Input Format

The first line contains an integer N. Each of the following N lines contains a pair of integers. The i-th line contains a pair of numbers, $V_i,P_i$, separated by space.  

Constraints

$1\leq N\leq5\times10^5$ 

$0\leq V_i\leq10^9$ 

$0\leq P_i\leq10^5$  

Output Format

Derive the maximum score given by return (score);.

Sample Input
4
4 2
0 2
4 0
3 4

Sample Output
7

Explanation

In the best case, the first and second function call in Go variable $\textbf{way}$ will take value 2, while in the other calls it will be equal to 1 then the final score will be equal to the value of 7.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import bisect
N = int(input())
L = []
for n in range(N):
	A = list(map(int, input().split()))
	L.append(A)
Pareto = [[0, 0]]
for i in range(0, len(L) - 1):
	A = L[i]
	v = A[0]
	p = A[1]
	if p == 0:
		Pareto = list(([t[0] + v, t[1] - 1] for t in Pareto if t[1] >= 1))
	else:
		M = Pareto[-1]
		if M[1] >= p:
			Pareto = list(([t[0] + v, t[1] - 1] for t in Pareto if t[1] >= 1))
		else:
			Pareto = list(([t[0] + v, t[1] - 1] for t in Pareto if t[1] >= 1 and (t[0] + v > M[0] or t[1] > p)))
			bisect.insort(Pareto, [M[0], p - 1])
print(Pareto[len(Pareto) - 1][0] + L[len(L) - 1][0])


import sys
N = int(sys.stdin.readline())
rung = []
for line in reversed(sys.stdin.readlines()):
	line = [int(x) for x in line.split()]
	if rung == []:
		rung.append([line[0], 0])
		continue
	nextRung = [[0, 0]]
	if line[1] != 0:
		tempRung = []
		for path in rung:
			if path[1] <= line[1]:
				tempRung.append([path[0], 0])
		nextRung.remove([0, 0])
		nextRung.append(max(tempRung))
	for path in rung:
		if path[0] + line[0] > nextRung[0][0]:
			if path[1] == 0:
				nextRung.append([path[0] + line[0], 2])
			else:
				nextRung.append([path[0] + line[0], path[1] + 1])
	rung = nextRung
print(rung[0][0])


from heapq import heappop, heappush

class VP:

	def __init__(self, score, energy):
		self.score = score
		self.energy = energy

	def __lt__(self, other):
		return self.score < other.score
N = int(input())
vps = [0] * N
heap = []
for i in range(N):
	vps[i] = VP(*list(map(int, input().split())))
(score, energy) = (vps[0].score, vps[0].energy)
for i in range(1, N - 1):
	heappush(heap, VP(score + vps[i].score, i + vps[i].energy))
	if i >= energy:
		best = heappop(heap)
		while best.energy <= i:
			best = heappop(heap)
		(score, energy) = (best.score, best.energy)
print(sum((vps[i].score for i in range(N))) - score)


def run():
	N = int(input().strip())
	states = {0: 0}
	for step in range(N - 1):
		(v, p) = map(int, input().split())
		pm1 = p - 1
		new_states = {}
		for (energy, score) in states.items():
			if p > energy:
				new_states[pm1] = max(new_states.get(pm1, -1), score)
			if energy > 0:
				new_states[energy - 1] = max(new_states.get(energy - 1, -1), score + v)
		states = new_states
		prev_score = None
		for (energy, score) in reversed(sorted(states.items())):
			if prev_score is not None and score <= prev_score:
				del states[energy]
			prev_score = score
	(v, p) = map(int, input().strip().split(' '))
	return max(states.values()) + v
result = run()
print(result)


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


def run():
	N = int(input().strip())
	states = {0: 0}
	for step in range(N - 1):
		(v, p) = map(int, input().split())
		pm1 = p - 1
		new_states = {}
		for (energy, score) in states.items():
			if p > energy:
				new_states[pm1] = max(new_states.get(pm1, -1), score)
			if energy > 0:
				new_states[energy - 1] = max(new_states.get(energy - 1, -1), score + v)
		states = new_states
		prev_score = None
		for (energy, score) in reversed(sorted(states.items())):
			if prev_score is not None and score <= prev_score:
				del states[energy]
			prev_score = score
	(v, p) = map(int, input().strip().split(' '))
	return max(states.values()) + v
result = run()
print(result)


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import heapq
import threading
from collections import defaultdict
import itertools
vp_all = [[int(x) for x in input().split()] for _ in range(int(input()))]
n = len(vp_all)
result_all = set()

def calc_a():
	hh = []
	heapq.heappush(hh, (0, n - 1, ()))
	cache_best = {}
	inds_free_recharge = [i for (i, (v, p)) in enumerate(vp_all) if v == 0]
	while len(hh) > 0 and len(result_all) == 0:
		(points_lost, i_last, hist_recharge) = heapq.heappop(hh)
		if i_last == 0:
			result_all.add(points_lost)
			break
		if i_last in cache_best:
			if points_lost >= cache_best[i_last]:
				continue
		cache_best[i_last] = points_lost
		i_min = max((i for i in inds_free_recharge if i < i_last), default=0)
		lowest_cost = None
		for (i, v, p) in ((i_rel + i_min, v, p) for (i_rel, (v, p)) in enumerate(vp_all[i_min:i_last]) if p - (i_last - (i_rel + i_min)) >= 0):
			if lowest_cost is None or v < lowest_cost:
				lowest_cost = v
				heapq.heappush(hh, (points_lost + v, i, hist_recharge + (i,)))

def calc_b():
	cumsum_vv = list(itertools.accumulate((v for (v, p) in vp_all), lambda a, b: a + b))
	max_charging_points = 50
	charging_inds_priorized = [0] + [i_vp[0] for i_vp in sorted(enumerate(vp_all[1:], 1), key=lambda x: x[1][0])]
	while len(result_all) == 0:
		charging_ind_cands = sorted(charging_inds_priorized[:max_charging_points])
		m = len(charging_ind_cands)
		hh = []
		heapq.heappush(hh, (0, 0, 0, 0, ()))
		while len(hh) > 0 and len(result_all) == 0:
			(points_lost, minus_i, minus_energy, next_cand_index, hist_recharge) = heapq.heappop(hh)
			energy = -minus_energy
			if energy < 0:
				continue
			if next_cand_index >= m or charging_ind_cands[next_cand_index] == n - 1:
				score = sum((v for (v, p) in vp_all)) - points_lost
				result_all.add(points_lost)
				break
			i = charging_ind_cands[next_cand_index]
			if next_cand_index < m - 1:
				i_after = charging_ind_cands[next_cand_index + 1]
			else:
				i_after = n - 1
			(v, p) = vp_all[i]
			if p > energy:
				heapq.heappush(hh, (points_lost + v, -i_after, -(p - (i_after - i)), next_cand_index + 1, hist_recharge + (i,)))
			if energy > 0 and (v > 0 or energy >= p):
				heapq.heappush(hh, (points_lost, -i_after, -(energy - (i_after - i)), next_cand_index + 1, hist_recharge))
		else:
			if max_charging_points >= n:
				assert False, 'no solution found'
			else:
				max_charging_points *= 2
thread_all = [threading.Thread(target=f) for f in [calc_a, calc_b]]
for th in thread_all:
	th.start()
for th in thread_all:
	th.join()
points_lost = result_all.pop()
score = sum((v for (v, p) in vp_all)) - points_lost
print(score)


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import math
import os
import random
import re
import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, oo) = input().split()
	V[i] = int(v_item)
	P[i] = int(oo)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		g = games[j]
		if g[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < g[0]:
			maxVal = g[0]
		else:
			del games[j]
		g[0] += V[i]
		g[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
N = int(input())
(V, P) = ([None] * N, [None] * N)
for i in range(N):
	(v_item, p_item) = input().split()
	V[i] = int(v_item)
	P[i] = int(p_item)
games = []
for i in range(N):
	maxVal = -1
	games.sort(key=itemgetter(1))
	for j in range(len(games) - 1, -1, -1):
		game = games[j]
		if game[1] == 0:
			del games[0:j + 1]
			break
		if maxVal < game[0]:
			maxVal = game[0]
		else:
			del games[j]
		game[0] += V[i]
		game[1] += -1
	if maxVal == -1:
		maxVal = 0
	games.append([maxVal, P[i]])
print(max(games, key=itemgetter(0))[0])


import sys
from operator import itemgetter
nest = int(input())
(vadiley, pisuku) = ([None] * nest, [None] * nest)
for i in range(nest):
	(ramana, loadatahli) = input().split()
	vadiley[i] = int(ramana)
	pisuku[i] = int(loadatahli)
gamabagsd = []
for i in range(nest):
	vanammmmmsa = -1
	gamabagsd.sort(key=itemgetter(1))
	for j in range(len(gamabagsd) - 1, -1, -1):
		game = gamabagsd[j]
		if game[1] == 0:
			del gamabagsd[0:j + 1]
			break
		if vanammmmmsa < game[0]:
			vanammmmmsa = game[0]
		else:
			del gamabagsd[j]
		game[0] += vadiley[i]
		game[1] += -1
	if vanammmmmsa == -1:
		vanammmmmsa = 0
	gamabagsd.append([vanammmmmsa, pisuku[i]])
print(max(gamabagsd, key=itemgetter(0))[0])