minMoney

DAN đang cần đổi số tiền n đồng về tiền lẻ, biết mệnh giá các tờ tiền lẻ DAN có thể đổi được biểu diễn ở mảng arr, biết rằng có vô số tờ tiền lẻ. Tuy nhiên DAN lại không muốn cầm quá nhiều tờ tiền nên muốn đổi sao cho số tờ tiền là ít nhất. Hãy giúp DAN tìm số tờ tiền đó, nếu không thể đổi được thì hãy trả về 0.

Ví dụ:

Với n = 10 và arr = [1,2,3] thì minMoney = 4;

Có rất nhiều cách đổi tiền:

• 10 tờ 1 đồng.
• 5 tờ 2 đồng.
• 3 tờ 3 đồng và 1 tờ 1 đồng.
• 3 tờ 2 đồng và 4 tờ 1 đồng.
• …

Nhưng ta thấy cách đổi ra 3 tờ 3 đồng và 1 tờ 1 đồng là ít tờ tiền nhất (4 tờ), nên kết quả sẽ là 4.

Đầu vào/Đầu ra

• [Giới hạn thời gian] 0.5s với C++, 3s với Java & C#, 4s Python, GO và Js.

• [Đầu vào]:
  Integer n
  1 <= n <= 10^8
  Array.Integer arr
  0 <= arr.length <= 100
1 <= arr[i] <= 10000
arr chứa các phần tử đôi một khác nhau
• [Đầu ra] Integer