Problem Introduction

This problem is about implementing an algorithm for the knapsack without repetitions problem.

Problem Description

Task.In this problem, you are given a set of bars of gold and your goal is to take as much gold as possible into you bag. There is just one copy of each bar and for each bar you can either take it or not(hence you cannot take a fraction of a bar).

Input Format.The first line of the input contains the capacity \(W\) of a knapsack and the number \(n\) of bars of gold. The next line contains \(n\) integers \(w_0, w_1. \cdots, w_{n-1}\) defining the weights of the bars of gold.

Constraints.\(1 \leq W \leq 10^4\); \(1 \leq n \leq 300\); \(0 \leq w_0, \cdots, w_{n-1} \leq 10^5\).

Output Format.Output the maximum weight of gold that fits into a knapsack of capacity \(W\).

Sample 1.
Input:

10 3
1 4 8

Output:

9

Solution