편의점에서 일을하고 있는 정희는 계산을 마치고 잔돈을 거슬러 주어야 합니다.

잔돈을 거슬러 주기 위해 최소 개수의 동전과 지폐를 사용해야 합니다. 이때, 사용된 동전과 지폐의 최소 개수를 반환하는 solution 함수를 작성하세요.

잔돈의 총액이 amount로 주어지며, 항상 단위에 맞는 금액만 입력됩니다. 만약 거슬러 줄 수 없는 경우에는 -1을 반환하세요.

입출력 예시

예시 1:

• 입력: coins = [10, 5, 25, 1], amount = 30

• 출력: 2

• 설명: 30원을 거슬러주기 위해 25원 동전 1개와 6원 동전 1개를 사용합니다.

예시 2:

• 입력: coins = [9, 4, 1], amount = 12

• 출력: 3

• 설명: 12원을 거슬러주기 위해 4원짜리 동전 3개를 사용합니다.

예시 3:

• 입력: coins = [3, 7], amount = 5

• 출력: -1

• 설명: 주어진 동전으로는 5원을 정확히 만들 수 없으므로 -1을 반환합니다.

예시 4:

• 입력: coins = [1, 5, 7], amount = 0

• 출력: 0

제한 사항

• 1 ≤ coins.length ≤ 10

• 1 ≤ coins[i] ≤ 2³¹ -1

• 0 ≤ amount ≤ 10³

• coins[i]는 서로 중복되지 않는 값입니다.