output_description: Print the number of attacks Serval needs to make before winning.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H A
attempt: import numpy as np
  from sys import stdin
  
  
  ## This code doesn't pass the test
  # def get_result(data):
  #     H, N = data[0]
  #     A_and_B = np.array(data[1:])
  #     calc_efficient = np.array(list(map(lambda x: float(x[0] / x[1]), A_and_B)))
  #     sorted_index = np.argsort(-calc_efficient)
  
  #     cost = 0
  #     remainder_H = H
  #     for i in sorted_index:
  #         A, B = A_and_B[i]
  #         quotient = remainder_H // A
  #         if quotient > 0:
  #             cost += B * quotient
  #             remainder_H = remainder_H - A * quotient
  #         else:
  #             if remainder_H > 0:
  #                 continue
  #             else:
  #                 break
  
  #     return cost
  
  ## 答え (DP, ナップザック問題の典型らしい)
  # 自分の解法は典型的なハマり方をしたっぽい
  
  
  def get_result(data):
      # 初期化
      H, N = data[0]
      A_and_B = np.array(data[1:])
      A = A_and_B[:, 0].reshape(-1)
      B = A_and_B[:, 1].reshape(-1)
  
      # 最小化問題だから無限で初期化
      # DP[j] = Aの和が j の時の最小コスト (魔力)
      # 計算量は、O(NH)なのでHが少なくなるようにテーブルは作る
      inf = float("inf")
      # N × H (制約条件) のテーブルを作成
      dp = [inf for j in range(H + 1)]
      # 初期値
      dp[0] = 0
  
      # DP (コードはなんとなく理解できた)
      for i in range(H):
          for j in range(N):
              # 魔力1つずつについてloopさせる
              if (i + 1) - A[j] < 0:
                  dp[i + 1] = min(dp[i + 1], dp[0] + B[j])
              else:
                  dp[i + 1] = min(dp[i + 1], dp[i + 1 - A[j]] + B[j])
  
      return dp[H]
  
  
  if __name__ == "__main__":
      raw_data = [val.rstrip("\n") for val in stdin.readlines()]
      data = [list(map(int, val.split(" "))) for val in raw_data]
      result = get_result(data)
      print(result)
  
problem_description: Statement
  
  Serval is fighting with a monster.
  
  The _health_ of the monster is H.
  
  In one attack, Serval can decrease the monster's health by A. There is no
  other way to decrease the monster's health.
  
  Serval wins when the monster's health becomes 0 or below.
  
  Find the number of attacks Serval needs to make before winning.
samples: [{"input": "10 4", "output": "3\n    \n\n  * After one attack, the monster's health will be 6.\n  * After two attacks, the monster's health will be 2.\n  * After three attacks, the monster's health will be -2.\n\nThus, Serval needs to make three attacks to win.\n\n* * *"}, {"input": "1 10000", "output": "1\n    \n\n* * *"}, {"input": "10000 1", "output": "10000"}]