Gold Knapsack Problem

You are given a knapsack with a maximum weight capacity \(C\) and a set of gold pieces, each with a specified weight. Your task is to determine the maximum total weight of gold that can be carried in the knapsack without exceeding its capacity. Each gold piece can be taken at most once.

This is a subset sum problem where you need to choose a subset of the provided weights that has the largest possible sum without exceeding \(C\). The problem requires the use of dynamic programming techniques to efficiently compute the answer.

Example:

Input:
50
3
10 20 30

Output:
50

In the example above, the best selection is to take the gold pieces weighing 10, 20, and 30 to perfectly fill the knapsack.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line of input contains a single integer \(C\) representing the capacity of the knapsack.
2. The second line contains an integer \(N\), the number of gold pieces available.
3. The third line contains \(N\) space-separated integers where each integer represents the weight of a gold piece.

outputFormat

Output a single integer to standard output (stdout) representing the maximum total weight of gold that can be carried without exceeding the knapsack's capacity.

50
3
10 20 30

50