Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h+1):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h+1):
            tmp = dp[j] + w
            if dp[j] != INF and tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
 
h, n = [int(item) for item in input().split()]
MAX_LEN = h + 10**4 + 1
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(n):
    v, w = map(int, input().split())
    for j in range(h+1):
        if dp[j] != INF and dp[j] + w < dp[j+v]:
            dp[j+v] = dp[j] + w
ans = min(dp[h:])
print(ans)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * (MAX_LEN * (n + 1))
dp[0] = 0
for i in range(1, n+1):
    v, w = ab[i-1]
    offset = i * MAX_LEN
    offset_before = offset - MAX_LEN
    for j in range(MAX_LEN):
        if j < v:
            dp[offset+j] = dp[offset_before+j]
        elif dp[offset_before+j] > dp[offset+j-v] + w:
            dp[offset+j] = dp[offset+j-v] + w
        else:
            dp[offset+j] = dp[offset_before+j]
ans = min(dp[n*(MAX_LEN) + h:])
print(ans)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * (MAX_LEN * (n + 1))
dp[0] = 0
for i in range(1, n+1):
    v, w = ab[i-1]
    for j in range(MAX_LEN):
        if j < v:
            dp[i*MAX_LEN+j] = dp[(i-1)*MAX_LEN+j]
        elif dp[(i-1)*MAX_LEN+j] > dp[i*MAX_LEN + j-v] + w:
            dp[i*MAX_LEN+j] = dp[i*MAX_LEN+j-v] + w
        else:
            dp[i*MAX_LEN+j] = dp[(i-1)*MAX_LEN+j]
ans = min(dp[n*(MAX_LEN) + h:])
print(ans)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n+1):
    v, w = ab[i-1]
    for j in range(2 * 10**4):
        if j < v:
            dp[i][j] = dp[i-1][j]
        elif dp[i-1][j] > dp[i][j-v] + w:
            dp[i][j] = dp[i][j-v] + w
        else:
            dp[i][j] = dp[i-1][j]
ans = min(dp[n][h:])
print(ans)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
    v = ab[i][0]
    w = ab[i][1]
    for j in range(10**4):
        if dp[i][j] == INF:
            continue
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j + v] = min(dp[i][j + v], dp[i][j] + w)
        dp[i][j+v] = min(dp[i][j+v], dp[i][j] + w)
ans = min(dp[n][h:])
print(ans)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()