s02228. 木料下料 未做

仓库里有 $K$ 根原木，每根长度都是 $L$。现在有 $m$ 张订单，第 $i$ 张订单要求切出 $c_i$ 段长度为 $l_i$ 的木料；只有整张订单全部完成，才能拿到这张订单的收益 $v_i$。原木可以任意切割，余料直接丢弃。小杨想知道，他最多能拿到多少收益。

第一行三个整数 $K,L,m$。接下来 $m$ 行，每行三个整数 $l_i,c_i,v_i$。

一行一个整数，最大总收益。

• 对于 30% 的数据：$m\le 4$
• 对于 60% 的数据：$m\le 6$
• 对于 100% 的数据：$1\le m\le 8$，$1\le K\le 5$，$1\le L\le 100$，$1\le c_i\le 10$，$1\le l_i\le L$，$1\le v_i\le 100$