최소 동전 개수

시간 제한1초메모리 제한128 MB

요약

동전 종류와 존이 가진 각 동전의 개수, 상점의 무제한 거스름돈이 주어질 때, 존이 T센트 이상을 지불하고 정확히 거스름돈을 받는 데 드는 최소 동전 수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

농부 존은 농장 용품을 사러 시내에 나왔다. 그는 매우 효율적인 사람이라, 물건 값을 낼 때 항상 오가는 동전의 총 개수가 최소가 되도록 지불한다. 즉, 지불에 사용하는 동전의 개수와 거스름돈으로 받는 동전의 개수의 합을 최소로 만든다. 이 최솟값을 구하여라.

농부 존은 $T$ 센트( $1 \le T \le 10{,}000$ )어치의 용품을 사려고 한다. 화폐 체계에는 서로 다른 동전이 $N$ 가지( $1 \le N \le 100$ ) 있으며, 각 동전의 가치는 $V_1, V_2, \dots, V_N$ ( $1 \le V_i \le 120$ )이다. 농부 존은 가치가 $V_1$ 인 동전을 $C_1$ 개, $V_2$ 인 동전을 $C_2$ 개, $\dots$ , $V_N$ 인 동전을 $C_N$ 개 가지고 있다( $0 \le C_i \le 10{,}000$ ). 가게 주인은 모든 종류의 동전을 무한히 가지고 있으며, 항상 가장 효율적인(동전 개수가 최소가 되는) 방법으로 거스름돈을 준다. 단, 농부 존은 정확한 거스름돈을 받을 수 있는 방식으로 지불해야 한다.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $T$ .
둘째 줄: 공백으로 구분된 $N$ 개의 정수 $V_1, V_2, \dots, V_N$ (동전의 가치).
셋째 줄: 공백으로 구분된 $N$ 개의 정수 $C_1, C_2, \dots, C_N$ (각 동전의 개수).

출력

첫째 줄: 지불과 거스름돈에 사용된 동전 개수의 최솟값을 나타내는 정수 하나. 농부 존이 정확히 지불하고 정확한 거스름돈을 받는 것이 불가능하면 $-1$ 을 출력한다.

힌트

$T = 70$ 인 경우, 농부 존은 50센트 동전과 25센트 동전으로 75센트를 지불하고 거스름돈으로 5센트 동전 하나를 받는다. 거래에 사용된 동전은 모두 3개이다.

예제5

예제 1
입력
```
3 70
5 25 50
5 2 1
```
예상 출력
```
3
```
예제 2
입력
```
1 5
1
100
```
예상 출력
```
5
```
예제 3
입력
```
1 3
5
1
```
예상 출력
```
-1
```
예제 4
입력
```
3 75
5 25 50
5 2 1
```
예상 출력
```
2
```
예제 5
입력
```
2 4
1 5
3 2
```
예상 출력
```
2
```