Challenge: Pack the Bag

Lab C++ Intermediate 20 points

Read the capacity W and n items (weight, value), each usable once. Print the best total value that fits.

Input

Line 1: W n (W ≤ 1000, n ≤ 100). Then n lines weight value.

Output

The best value.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

dp[w] = best value with capacity w.

Loop w downwards so each item is used at most once.

Solution explanation

Going down over w means dp[w − weight] is still the value from before this item: one row instead of a table.

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int W, n;
    cin >> W >> n;
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int wt;
        long long val;
        cin >> wt >> val;
        for (int w = W; w >= wt; w--) dp[w] = max(dp[w], dp[w - wt] + val);
    }
    cout << dp[W] << endl;
    return 0;
}

Output

Answer