Untitled

public class Main {
    public static List<Integer> findElementsForSum(int[] nums, int k) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        boolean[][] included = new boolean[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j >= nums[i - 1]) {
                    if (dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]) {
                        dp[i][j] = true;
                        included[i][j] = true;
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        List<Integer> elementsForSum = new ArrayList<>();
        int i = n, j = k;
        while (i > 0 && j > 0) {
            if (included[i][j]) {
                elementsForSum.add(nums[i - 1]);
                j -= nums[i - 1];
            }
            i--;
        }

        return elementsForSum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int neededSum = scanner.nextInt();
        int numberOfMoney = scanner.nextInt() * 2;
        int[] nums = new int[numberOfMoney];

        for (int i = 0; i < numberOfMoney; i += 2) {
            nums[i] = scanner.nextInt();
            nums[i + 1] = nums[i];
        }
        long startTime = System.nanoTime();
        List<Integer> elements = findElementsForSum(nums, neededSum);
        long endTime = System.nanoTime();
        if (!elements.isEmpty()) {
            System.out.println(elements);
        } else {
            System.out.println(-1);
        }
    }
}