Maximum Number of Paintings

You are given a total available wall space \(W\) and a collection of paintings where each painting requires a certain amount of wall space. Your task is to determine the maximum number of paintings that can be hung on the wall such that the total used space does not exceed \(W\).

Formally, given a list of integers \(a_1, a_2, \dots, a_n\) representing the wall space requirements of each painting, find the largest integer \(k\) such that there exists a subset \(S\) with \(|S| = k\) and \(\sum_{i \in S} a_i \leq W\). The optimal strategy is to choose the paintings with the smallest space requirements first.

inputFormat

The input is given on standard input and consists of the following:

• The first line contains an integer \(W\) representing the total available wall space.
• The second line contains an integer \(n\) denoting the number of paintings.
• The third line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the wall space requirement of each painting.

outputFormat

Output a single integer, the maximum number of paintings that can be displayed without exceeding the wall space \(W\).

10
5
3 8 5 2 4

3