inf = 10**9
n = int(input())
t = [0] * n
p = [0] * n
for i in range(n):
t[i], p[i] = map(int, input().split())
d = [-1] * n
def go(index):
if index > n:
return -inf
if index == n:
return 0
if d[index] != -1:
return d[index]
a = p[index] + go(index + t[index])
b = go(index + 1)
d[index] = max(a, b)
return d[index]
print(go(0))
재귀함수를 통해 구하고 + sum 대신 메모이제이션을 추가하여 dp로 푼다