Daniel is a planning engineer of an Marine Logistic Corporation. His daily work is to plan & manage the process of loading containers into ships. There are N containers, each with its own weights (tons) and price value (MYR) that need to be loaded into a ship that has maximum capacity of W (tons).
Help him to identify which containers should be loaded into the ship so that the total weight does not exceed the ship capacity and the total price value is highest.
On the first line you are given W and N. N lines follow with two integer on each line describing the weight (tons) & price value (MYR) of each container in that order. Notes that (1 ≦ N ≦ 1000), (100 ≦ W ≦ 1000000). Each container weight is less than '10000'.
You should output a single integer which is the maximum price value of selected containers.
As the ship capacity is 4, select container 1st & 4th will get highest value: 8 + 5 = 13