【題目描述】

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

【輸入】

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

【輸出】

僅一行，一個(gè)數，表示最大總價(jià)值。

【輸入樣例】

10 4

2 1

3 3

4 5

7 9

【輸出樣例】

12