【題目描述】

一個(gè)旅行者有一個(gè)最多能裝V??公斤的背包，現在有n??件物品，它們的重量分別是W1??1，W2??2，...,Wn????，它們的價(jià)值分別為C1??1,C2??2...Cn????。有的物品只可以取一次(0101背包)，有的物品可以取無(wú)限次（完全背包)，有的物品可以取的次數有一個(gè)上限(多重背包)。求解將哪些物品裝入背包可使這些物品的費用總和不超過(guò)背包容量，且價(jià)值總和最大。

【輸入】

第一行:二個(gè)整數，M??(背包容量，M≤200??≤200)，N??(物品數量，N≤30??≤30);

第22..N+1??+1行:每行三個(gè)整數Wi????,Ci????,Pi????，前兩個(gè)整數分別表示每個(gè)物品的重量，價(jià)值，第三個(gè)整數若為00，則說(shuō)明此物品可以購買(mǎi)無(wú)數件，若為其他數字，則為此物品可購買(mǎi)的最多件數(P??)。

【輸出】

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

【輸入樣例】

10? 3

2? 1? 0

3? 3? 1

4? 5? 4

【輸出樣例】

11

【提示】

【樣例說(shuō)明】

選第一件物品11件和第三件物品22件。