/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>

constexpr int32_t kMaxNumberOfCoinTypes = 20;
constexpr int32_t kMaxAmountOfPayment = 50000;

void CallCoinChangingProblem(std::istream &input_stream);

class CoinChangingProblem {
 public:
  CoinChangingProblem() noexcept;
  ~CoinChangingProblem() noexcept;
  void AddCoinValue(const int32_t coin_value);
  int32_t FindNumberOfMinimumNumberOfCoins(const int32_t amount_of_payment) noexcept;

 private:
  CoinChangingProblem(const CoinChangingProblem &obj) = delete;
  CoinChangingProblem &operator=(const CoinChangingProblem &obj) = delete;
  CoinChangingProblem(CoinChangingProblem &&obj) = delete;
  CoinChangingProblem &operator=(CoinChangingProblem &&obj) = delete;

 private:
  int32_t number_of_coin_types_;
  int32_t coin_values_[kMaxNumberOfCoinTypes];
  int32_t minimum_number_of_coins_[kMaxAmountOfPayment + 1];
};

void CallCoinChangingProblem(std::istream &input_stream) {
  input_stream.tie(0);
  std::ios::sync_with_stdio(false);
  CoinChangingProblem *articulation_point = new CoinChangingProblem();
  try {
    int32_t amount_of_payment, number_of_coin_types;
    input_stream >> amount_of_payment >> number_of_coin_types;
    for (int32_t i = 0; i < number_of_coin_types; ++i) {
      int32_t coin_value;
      input_stream >> coin_value;
      articulation_point->AddCoinValue(coin_value);
    }
    std::cout << articulation_point->FindNumberOfMinimumNumberOfCoins(amount_of_payment) << std::endl;
  } catch (...) {
    std::cerr << "ERROR: CallCoinChangingProblem()" << std::endl;
    delete articulation_point;
    throw;
  }
  delete articulation_point;
}

// ****************************************************
CoinChangingProblem::CoinChangingProblem() noexcept : number_of_coin_types_(0) {}

CoinChangingProblem::~CoinChangingProblem() noexcept {}

void CoinChangingProblem::AddCoinValue(const int32_t coin_value) {
  if (number_of_coin_types_ >= kMaxNumberOfCoinTypes) {
    std::cerr << "ERROR: AddCoinValue(): number_of_coin_types_ exceeded a limit = " << kMaxNumberOfCoinTypes
              << std::endl;
  }
  const int32_t index_stored = number_of_coin_types_;
  coin_values_[index_stored] = coin_value;
  ++number_of_coin_types_;
}

int32_t CoinChangingProblem::FindNumberOfMinimumNumberOfCoins(const int32_t amount_of_payment) noexcept {
  for (int32_t temp_amount = 1; temp_amount <= amount_of_payment; ++temp_amount) {
    minimum_number_of_coins_[temp_amount] = INT32_MAX;
    for (int32_t index_coin = 0; index_coin < number_of_coin_types_; ++index_coin) {
      const int32_t remaining_amount = temp_amount - coin_values_[index_coin];
      if (remaining_amount == 0) {
        minimum_number_of_coins_[temp_amount] = 1;
      } else if (remaining_amount > 0) {
        const int32_t number_of_coins_of_remaining_amount = minimum_number_of_coins_[remaining_amount];
        const int32_t candidate_of_minimum_number_of_coins = number_of_coins_of_remaining_amount + 1;
        if (candidate_of_minimum_number_of_coins < minimum_number_of_coins_[temp_amount]) {
          minimum_number_of_coins_[temp_amount] = candidate_of_minimum_number_of_coins;
        }
      }
    }
  }
  return minimum_number_of_coins_[amount_of_payment];
}

int main() {
  try {
    CallCoinChangingProblem(std::cin);
  } catch (...) {
    std::cerr << "ERROR: main()" << std::endl;
  }
  return 0;
}



Measured memory_bytes: 3184