Buggy python submission (verdict: Runtime Error):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()



Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Runtime Error):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()



Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Runtime Error):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
        return bi


    print(calc(H))



if __name__ == "__main__":
    resolve()



Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n, m = divmod(H, a)
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if m:
            n += 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()



Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        h = H
        i = 1
        while h >= i:
            S.append((a*i, b*i))
            h -= i
            i <<= 1
        if h:
            S.append((a*h, b*h))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()



Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()


Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 > um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            if u1 <= um:
                heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()


Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 > um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()


Fixed submission:
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



if __name__ == "__main__":
    resolve()