【題目描述】

設有n??種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為M??，今從n??種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M??，而價值的和為最大。

【輸入】

第一行:兩個整數，M??(背包容量，M≤200??≤200)和N??(物品數量，N≤30??≤30);第22..N＋1??＋1行:每行二個整數Wi????,Ci????，表示每個物品的重量和價值。

【輸出】

僅一行，一個數，表示最大總價值。

【輸入樣例】

10 4

2 1

3 3

4 5

7 9

【輸出樣例】

max=12