문제 설명

당신은 편의점 자판기 알바생입니다. 자판기에는 각 동전별로 제한된 수량이 있습니다: • 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