10875

d = [0] * 21
d[1], d[2] = 1, 1
n = int(input())

for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

2748

d = list()
d.append(0)
d.append(1)
n = int(input())

for i in range(2, n + 1):
d.append(d[i - 1] + d[i - 2])

print(d[n])

2156

# 포도주 시식

import sys

input = sys.stdin.readline

n = int(input())
wine = [0] * 10001
for i in range(n):
  wine[i] = int(input())

d = [0] * 10001
d[0], d[1], d[2] = wine[0], wine[0] + wine[1], max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])

for i in range(3, n+1):
  d[i] = max(d[i -2] + wine[i], d[i - 3] + wine[i - 1] + wine[i], d[i - 1])

print(d[n])

1463

# 1로 만들기

n = int(input())
d = [0] * (n + 1) # 각 인덱스 번호를 원소로 가지도록 배열 초기화, 각 인덱스의 최소연산횟수를 저장할 것임

for i in range(2, n+1):
  d[i] = d[i - 1] + 1

  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)

print(d[n])

12865

# 평범한 배낭
# 냅색(Knapsack) 알고리즘

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
inputs = [[0, 0]]
d = [[0] * (k+1) for _ in range(n+1)]

for _ in range(n):
    inputs.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = inputs[i][0]
        v = inputs[i][1]
        if w > j:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j-w] + v, d[i-1][j])

print(d[n][k])