【題目描述】

一個旅行者有一個最多能裝M??公斤的背包，現(xiàn)在有n??件物品，它們的重量分別是W1??1，W2??2，...,Wn????.它們的價值分別為C1??1,C2??2,... ,Cn????，求旅行者能獲得最大總價值。

【輸入】

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

【輸出】

僅一行，一個數(shù)，表示最大總價值。

【輸入樣例】

10 4

2 1

3 3

4 5

7 9

【輸出樣例】

12