Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
sum = 0

while N >= 10:
  sum += N%10
  N = N//10

sum += N

if sum%9 == 0:
  print("Yes")
else:
  print("No")
  

Fixed submission:
N = list(input())
num = list(map(int,N))

sum = sum(num)

if sum%9 == 0:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
K = int(input())

r = 1
N = 0
while True:
    N += 7*(10**(r-1))
    if N%K ==0:
        break
    r += 1

print(r)

Fixed submission:
N,D = map(int,input().split())
X=[]
Y=[]
count = 0
for i in range(N):
    a,b = map(float,input().split())
    X.append(a)
    Y.append(b)
for i in range(N):
    if (X[i]**2+Y[i]**2)**(1/2) <= D:
        count += 1

print(count)

Buggy python submission (verdict: Runtime Error):
N,D = map(int,input().split())
X=[]
Y=[]
count = 0
for i in range(N):
    a,b = map(float,input().split())
    X.append(a)
    Y.append(b)
for i in range(N):
    if (X[i]^2+Y[i]^2)^(1/2) <= D:
        count += 1

print(count)


Fixed submission:
N,D = map(int,input().split())
X=[]
Y=[]
count = 0
for i in range(N):
    a,b = map(float,input().split())
    X.append(a)
    Y.append(b)
for i in range(N):
    if (X[i]**2+Y[i]**2)**(1/2) <= D:
        count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
K = int(input())

for i in range(K):
    if i = 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)

Fixed submission:
K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
K = int(input())

for i in range(K):
    if i = 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i)
        break
else:
    print(-1)

Fixed submission:
K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

if K%2==0:
    print(-1)

r = 1
N = 0

while True:
    N += 7*(10**(r-1))
    if N%K ==0:
        break
    r += 1

print(r)


Fixed submission:
K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

r = 1
N = 0
while True:
    N += 7*(10**(r-1))
    if N%K ==0:
        break
    r += 1

print(r)


Fixed submission:
K = int(input())

for i in range(K):
    if i == 0:
        N= 7%K
    else:
        N = (10*N+7)%K
    if N == 0:
        print(i+1)
        break
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
a = int(input())

ans = a(1+a+a**2)
print(int(ans))

Fixed submission:
a = int(input())

ans = a + a**2 + a**3
print(int(ans))
Buggy python submission (verdict: Runtime Error):
str = input()
if str.isupper()==TRUE:
  print("A")
else:
  print("a")

Fixed submission:
str = input()
if str.isupper()==True:
  print("A")
else:
  print("a")
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
price = list(map(int,input().split()))
priceN = sorted(price)
total = 0
for i in range(K):
  total += priceN[i]
price(total)

Fixed submission:
N,K = map(int,input().split())
price = list(map(int,input().split()))
priceN = sorted(price)
total = 0
for i in range(K):
  total += priceN[i]
print(total)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
An = list(map(int,input().split()))
mult =1
for i in An:
  mult *= i

if mult >10**18:
  print(-1)
else:
  print(mult)

Fixed submission:
N = int(input())
An = list(map(int,input().split()))

if 0 in An:
  print(0)

else:
  mult =1
  for i in An:
    mult *= i
    if mult > 10**18:
      print(-1)
      break

  else:
    print(mult)
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 998244353

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, S = LI()
    a = LI()
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dp[i][0] = dp[i-1][0] * 2 + 1
        dp[i][0] %= mod
    for i in range(N):
        for j in range(1, S+1):
            if j - a[i] >= 0:
                dp[i+1][j] = (dp[i][j-a[i]] % mod) + (dp[i][j] * 2 % mod)
            else:
                dp[i+1][j] = dp[i][j] * 2 % mod
            if j == a[i]:
                dp[i+1][j] += 1
            dp[i+1][j] %= mod
    print(dp[N][S])

main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 998244353

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, S = LI()
    a = LI()
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dp[i][0] = dp[i-1][0] * 2 + 1
        dp[i][0] %= mod
    for i in range(N):
        for j in range(1, S+1):
            if j - a[i] >= 0:
                dp[i+1][j] = (dp[i][j-a[i]] % mod) + (dp[i][j] * 2 % mod)
            else:
                dp[i+1][j] = dp[i][j] * 2 % mod
            if j == a[i]:
                dp[i+1][j] += 1
            dp[i+1][j] %= mod
    print(dp[N][S])

main()
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val
    visited = set()
    def dfs(v):
        visited.add(v)
        changed_i, before_val = update_dp(v)
        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[changed_i] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    visited = set()

    def dfs(v):
        visited.add(v)

        j = bisect.bisect_left(dp, A[v])
        before_val = dp[j]
        dp[j] = A[v]

        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[j] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()
Buggy python submission (verdict: Runtime Error):
def LI(): return [int(x) for x in sys.stdin.readline().split()]
n, m = LI()
if n == m:
  print("Yes")
else:
  print("No")

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, m = LI()
    if n == m:
        print("Yes")
    else:
        print("No")

main()

Buggy python submission (verdict: Runtime Error):
n, m = list(int, input().split())
if n == m:
  print("Yes")
else:
  print("No")

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, m = LI()
    if n == m:
        print("Yes")
    else:
        print("No")

main()
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    a, b = LI()
    gcd = math.gcd(a, b)
    print(a*b//gcd)
        

main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    a, b = LI()
    gcd = fractions.gcd(a, b)
    print(a*b//gcd)

main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
l = len(N)
if l % 2 == 1:
  ans = 0
else:
  ans = (S[:l//2] == S[l//2:])
if ans:
  print('Yes')
else:
  print('No')

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    t = S()
    if N % 2 > 0:
        print('No')
        return
    if t[:N//2] == t[N//2:]:
        print('Yes')
    else:
        print('No')

main()
Buggy python submission (verdict: Runtime Error):
s=input()
even = ["L","U","D"]
odd = ["R", "U", "D"]
f = false
for i in range(len(s)):
  if i%2:
    if s[i] not in even:
      f = True
  else:
    if s[i] not in odd:
      f = True
if f:
  print("No")
else:
  print("Yes")

Fixed submission:
s=input()
even = ["L","U","D"]
odd = ["R", "U", "D"]
f = False
for i in range(len(s)):
  if i%2:
    if s[i] not in even:
      f = True
  else:
    if s[i] not in odd:
      f = True
if f:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N, M = LI()
    A = LI()
    total = sum(A)
    discount = []
    for a in A:
        while a > 0:
            disc = (a+1)//2
            discount.append(disc)
            a -= disc
    discount = sorted(discount)[::-1]
    discount = discount[:M]
    print(total - sum(discount))
main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N, M = LI()
    A = LI()
    total = sum(A)
    discount = []
    for a in A:
        while a > 0:
            disc = (a+1)//2
            discount.append(disc)
            a -= disc
    discount = sorted(discount)[::-1]
    discount = discount[:M]
    print(total - sum(discount))
main()
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    r = I()
    print(3 * a * a)

main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    r = I()
    print(3 * r * r)

main()
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    L, R = LI()
    diff = R - L
    L %= 2019
    R = min(L + diff, R % 2019 + 2019)
    ans = inf
    for i in range(L, R):
        for j in range(L + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)

main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    L, R = LI()
    diff = R - L
    L %= 2019
    R = min(L + diff, R % 2019 + 2019)
    ans = inf
    for i in range(L, R):
        for j in range(L + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = map(int, input().split())
A = sorted(A) # ascending

B_C = []
for _ in range(M):
    b, c = map(int, input().split())
    B_C.append((b, c))
B_C = sorted(B_C, key=lambda x: x[1], reverse=True)

cur_a_ix = 0
ans = 0

for b, c in B_C:
    while b:
        if A[cur_a_ix] < c:
            ans += c
        else:
            break
        b -= 1
        cur_a_ix += 1
ans += sum(A[cur_a_ix:])
print(ans)
    


Fixed submission:
N, M = map(int, input().split())
A = map(int, input().split())
A = sorted(A) # ascending

B_C = []
for _ in range(M):
    b, c = map(int, input().split())
    B_C.append((b, c))
B_C = sorted(B_C, key=lambda x: x[1], reverse=True)

cur_a_ix = 0
ans = 0

for b, c in B_C:
    while b and cur_a_ix < len(A):
        if A[cur_a_ix] < c:
            ans += c
        else:
            break
        b -= 1
        cur_a_ix += 1
ans += sum(A[cur_a_ix:])
print(ans)
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = LI()
    num2match = {
        1: 2,
        2: 5,
        3: 5,
        4: 4,
        5: 5,
        6: 6,
        7: 3,
        8: 7,
        9: 6,
    }
    dp = ['' for _ in range(N+1)]
    for a in A:
        match_need = num2match[a]
        dp[match_need] = max(str(dp[match_need]), str(a))
    for i in range(N+1):
        for a in A:
            match_need = num2match[a]
            if i - match_need > 0:
                if dp[i-match_need] == '':
                    continue
                old = dp[i]
                new = str(a) + dp[i-match_need]
                if len(old) > len(new):
                    dp[i] = old
                elif len(new) > len(old):
                    dp[i] = new
                else:
                    dp[i] = max(old, new)
    print(dp[N])
main()



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = LI()
    num2match = {
        1: 2,
        2: 5,
        3: 5,
        4: 4,
        5: 5,
        6: 6,
        7: 3,
        8: 7,
        9: 6,
    }
    dp = ['' for _ in range(N+1)]
    for a in A:
        match_need = num2match[a]
        if 0 <= match_need <= N:
            dp[match_need] = max(str(dp[match_need]), str(a))
    for i in range(N+1):
        for a in A:
            match_need = num2match[a]
            if i - match_need > 0:
                if dp[i-match_need] == '':
                    continue
                old = dp[i]
                new = str(a) + dp[i-match_need]
                if len(old) > len(new):
                    dp[i] = old
                elif len(new) > len(old):
                    dp[i] = new
                else:
                    dp[i] = max(old, new)
    print(dp[N])
main()