现有N(N≤100)种魔法石和一个容量为V（1<=V<=50000）的背包。第i种魔法石最多有c[i]（1<=c[i]<=200）件可用，每个占用的空间是p[i]，价值是w[i]（1<=p[i],w[i]<=10000）。求解将哪些魔法石装入背包可使这些物品的容量总和不超过背包容量，且价值总和最大。

第一行为两个数字，即V和N。以下N行为每种物品的空间，价值和数量。

最大价值总和。

6 3
2 2 5
3 3 8
1 4 1

9