oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

lemonadestand Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

lemonadestand.html

Because Xin Yuan needed money to buy more hats in TF2, he decided to open a lemonade stand, and to do that, he needed money. Hence, he borrowed some from the most notorious loan shark in town. These sharks will come to his stand every day and ask for some money in the range of 1 to n. Because those loan sharks are not good at math, they can't count change very well and demanded exact amount to be paid. But Xin Yuan does not want to carry so many coins to his stand. Write a program to find the minimum number of coins he needs to carry.

Input

The first line contains the values n and k.

The next line contains k numbers, the value of coins available. The value 1 is guaranteed to be inside.

Output

Output the minimum number of coins he needs to carry.

Limits

1 ≤ n ≤ 4000, 1 ≤ k ≤ 1000.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

Explanation

He can carry 2 coins of value 1 and 2.

Sample Input 2

5 3
1 3 5

Sample Output 2

3

Explanation

He can carry 2 coins of value 1, and 1 coin of value 3.

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBMinimum
2021s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o lemonadestand -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.