Truck Maximum Value

Given a truck with a specific maximum capacity, your task is to determine the maximum total value of items that can be loaded onto the truck without exceeding its weight capacity. Each item can be used at most once.

This is a classic 0/1 knapsack problem. You are provided with an integer representing the truck's capacity and a list of items, where each item is defined by its weight and value. Use the following dynamic programming recurrence to solve the problem:

$$dp[i] = \max(dp[i],\ dp[i-w] + v)$$

where \(w\) and \(v\) represent the weight and value of an item, respectively.

inputFormat

The input is read from standard input (stdin). The first line contains an integer representing the truck's capacity. The second line contains an integer n representing the number of items. Each of the following n lines contains two space-separated integers: the weight and the value of an item.

outputFormat

Output the maximum total value that can be loaded onto the truck without exceeding its capacity. The output is written to standard output (stdout).## sample

4
3
2 3
1 2
3 4

6