[백준, 14501번] 퇴사

# Bottom Up 방식의 dp 풀이
# 하나씩 접근하면서 모든 과정을 거쳐야하기에 dp를 사용했다는 점!
import sys 
input = sys.stdin.readline
n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
dp = [0]*(n+1)

for i in range(n):
    for j in range(i+li[i][0], n+1):
        if dp[j] < dp[i]+li[i][1]: dp[j] = dp[i]+li[i][1]
print(dp[-1])

# Top Down
import sys 
input = sys.stdin.readline
n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
dp = [0]*(n+1)

for i in range(n-1,-1,-1):
    if i+li[i][0] > n: dp[i] = dp[i+1]
    else: dp[i] = max(dp[i+1], li[i][1]+dp[i+li[i][0]])
print(dp[0])

# 그리디 알고리즘으로 당장 보이는 부분부터 해보려 했지만
# 결국 해답을 찾기가 쉽지 않았다.
# !틀린 코드!
import sys
input = sys.stdin.readline
n = int(input())
start = hap = 0
li = [ list(map(int,input().split())) for _ in range(n)]
result = [li[0]]
while start <= n-1:
    t,p = result[-1]
    for i in range(start+1,start+t):
        if t > li[i][0] and p < li[i][1]: t,p = li[i][0], li[i][1]
    result[-1] = [t,p]
    start += t
    hap += p
    if start >= n or start+li[start][0] > n: break
    else: result.append(li[start])
print(hap)