問題説明

あなたはコンビニ自販機のバイトです。 自販機には各コインの数量制限があります: • 1000ウォン: 3枚 • 500ウォン: 5枚 • 100ウォン: 10枚 • 10ウォン: 10枚 お釣りを渡す時、**最小枚数のコイン**で渡さなければなりません。 ただし、自販機にあるコインだけ使えます!

入力

出力

制約条件

• •1 ≤ amount ≤ 10,000
• •amountは10の倍数
• •コイン保有量 ≥ 0

例

amount = 2730, coins = [1000×3, 500×5, 100×10, 10×10]

8

amount = 3500, coins = [1000×3, 500×0, 100×0, 10×0]

-1