Challenge: Pack the Bag

Lab Python Intermediate 20 points

Read the bag's capacity and n items (weight and value). Each item can be taken at most once. Print the largest total value that fits.

Input

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

Output

The best total value.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

dp[w] = best value with capacity w.

Loop w from W down to the item's weight, so each item is used at most once.

Solution explanation

Going downwards over w means dp[w − weight] still holds the value before this item was considered. That turns the 2D table into one row.

Show solution

W, n = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
dp = [0] * (W + 1)
for wt, val in items:
    for w in range(W, wt - 1, -1):
        dp[w] = max(dp[w], dp[w - wt] + val)
print(dp[W])

Output

Answer