이코테-DP) 효율적인 화폐구성

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

public class 효율적인화폐구성 {
	 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 m = Integer.parseInt(st.nextToken());
	        
	        int[] arr = new int[n];
	        int[] dp = new int[m+1]; // 0~10000까지
	        
	        for(int i=0;i<n;i++) {
	        	arr[i] = Integer.parseInt(br.readLine());
	        }
	        
	        
	        Arrays.fill(dp, 10001);
	        dp[0] = 0;
	        
	        for(int i=0;i<n;i++) {
	        	for(int j = arr[i];j<=m;j++) {
	        		if(dp[j-arr[i]] != 10001) { // 없어도 항상 10001이라 문제 없음
	        			dp[j] = Math.min(dp[j], dp[j-arr[i]] + 1); // 이거 생각해내는게 포인트
	        		}
	        	}
	        }
	        
	        if(dp[m] == 10001) {
	        	System.out.println(-1);
	        }
	        else {
	        	System.out.println(dp[m]);
	        }
	    }
}