import java.util.Scanner;

public class algo {
    static class Topic08 {
        public static void sortWeights(int[] weights){
            for(int i = 1; i < weights.length;i++){
                int getedEl = weights[i];
                int lastSorted = i - 1;
                while(lastSorted >= 0 && weights[lastSorted] < getedEl){
                    weights[lastSorted + 1] = weights[lastSorted];
                    lastSorted --;
                }
                weights[lastSorted + 1] = getedEl;
            }
        }
        public static void bagPackageCounterCheck(int capacity, int[] weights){
            int counter = 0;
            int index = 0;
            while(capacity > 0){
                if(index < weights.length){
                    if(capacity / weights[index] > 0){
                        capacity -= weights[index];
                        counter++;
                        System.out.println("Capacity is " + capacity + " Weight -> " + weights[index] + " Counter -> " + counter );
                    }else{

                        index++;
                    }

                }else{
                    System.out.print("The backpack cannot be filled with these packages!Rest is :" + capacity);
                    break;
                }
            }

        }

        public static void main(String[] args) {

            Scanner scanner = new Scanner(System.in);

            System.out.print("Enter backpack capacity --> ");
            int bagCapacity = scanner.nextInt();
            System.out.print("How many items you have for backpack (2-5) --> ");
            int items = scanner.nextInt();
            int[] itemWeight = new int[items];
            while(items < 2 || items > 5 ){
                System.out.print("Enter valid number -- > ");
                items = scanner.nextInt();
            }


            for(int i = 0; i < items;i++){
                System.out.printf("How many kilograms do the items weight? [%d] :",i);
                itemWeight[i] = scanner.nextInt();
            }



            sortWeights(itemWeight);

            bagPackageCounterCheck(bagCapacity , itemWeight);

        }
    }
}