거스름돈 계산하기 2

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] dp = new int[S+1]; //최소 거스름돈 수를 저장하는 dp 배열

        for(int i=1;i<=S;i++){ //0원일떄를 제외하고 모두 무한으로 설정
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int price = Integer.parseInt(st.nextToken()); //동전의 가격
            int count = Integer.parseInt(st.nextToken()); //동전을 가지고 있는 개수

            for(int j=0;j<=S;j++){ //0원부터 S원까지 반복
                if(dp[j]!=Integer.MAX_VALUE){ //현재 가격의 동전 개수가 무한이 아니라면
                    for(int k=1;k<=count;k++){ //동전의 개수만큼 반복
                        int idx = j+k*price; //다음 가격
                        if(idx>S){ //얻고자하는 가격을 넘으면 종료
                            break;
                        }
                        dp[idx] = Math.min(dp[idx],dp[j]+k); //원래 개수와 새로운 개수를 비교해서 최소값 저장
                    }
                }
            }
        }

        if(dp[S]==Integer.MAX_VALUE){ //해당 가격의 동전 개수가 무한이면 구할 수 없는 것
            System.out.println(-1);
        }
        else{ //구해져 있다면 출력
            System.out.println(dp[S]);
        }
    }
}