【題目描述】

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

【輸入】

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

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

【輸出】

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

【輸入樣例】

10? 3

2? 1? 0

3? 3? 1

4? 5? 4

【輸出樣例】

11

【提示】

【樣例說明】

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