Guest User

Untitled

a guest
Jan 26th, 2020
170
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. from functools import lru_cache
  3.  
  4. sys.setrecursionlimit(1000000)
  5.  
  6. H, N = map(int, input().split())
  7.  
  8. AB = []
  9. for i in range(N):
  10.     A, B = map(int, input().split())
  11.     AB.append((A, B))
  12.  
  13.  
  14. @lru_cache(maxsize=None)
  15. def f(h):
  16.     if h <= 0:
  17.         return 0
  18.     best = float("inf")
  19.     for a, b in AB:
  20.         val = b + f(h - a)
  21.         if val < best:
  22.             best = val
  23.         else:
  24.             # TLE if you don't have the break
  25.             # But I can't prove that it's safe to break
  26.             break
  27.     return best
  28.  
  29. # Sort by the most efficient spells
  30. AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
  31.  
  32. print(f(H))
RAW Paste Data