CoinChange

import java.util.Arrays;
import java.util.Scanner;

public class CoinChange {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read input: n (number of coins), x (target sum)
        int n = scanner.nextInt();
        int x = scanner.nextInt();

        // Read coin values into an array
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        // dp[i] stores the minimum number of coins needed to make sum 'i'
        // Initialize dp array with a large value (x + 1) representing infinity.
        // We use x + 1 because the maximum number of coins needed can't exceed x
        // (if we only used coins of value 1).  Any value larger than x is effectively infinity.
        int[] dp = new int[x + 1];
        Arrays.fill(dp, x + 1);

        // Base case: 0 coins are needed to make a sum of 0
        dp[0] = 0;

        // Iterate through all possible sums from 1 to x
        for (int i = 1; i <= x; i++) {
            // Iterate through each coin
            for (int coin : coins) {
                // If the current coin's value is less than or equal to the current sum 'i'
                if (coin <= i) {
                    // Check if using the current coin leads to a smaller number of coins
                    // dp[i - coin] represents the minimum coins needed to make the sum (i - coin)
                    // We add 1 to represent using the current coin.
                    // We take the minimum between the current dp[i] and the new value.
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // If dp[x] is still x + 1, it means no combination of coins could make the sum x
        // Otherwise, dp[x] contains the minimum number of coins needed.
        System.out.println(dp[x] > x ? -1 : dp[x]);

        scanner.close();
    }
}