‹ 上一题下一题 ›

s02228. 木料下料未做

1000 ms 256 MB 测试点 10 S-14·搜索进阶 S·算法自拟题 S-14 深度优先搜索搜索的剪枝优化

文件读写输入s02228.in输出s02228.out

题目描述

仓库里有 $K$ 根原木，每根长度都是 $L$ 。现有 $m$ 张订单，第 $i$ 张订单要求切出 $c_{i}$ 段长度为 $l_{i}$ 的木料；整张订单全部完成才能拿到收益 $v_{i}$ 。原木可以任意切割、余料丢弃。问最多能拿到多少收益。

输入格式

第一行三个整数 $K, L, m$ 。接下来 $m$ 行，每行三个整数 $l_{i}, c_{i}, v_{i}$ 。

输出格式

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

样例

输入

输出

数据范围

对于 30% 的数据： $m \leq 4$
对于 60% 的数据： $m \leq 6$
对于 100% 的数据： $1 \leq m \leq 8$ ， $1 \leq K \leq 5$ ， $1 \leq L \leq 100$ ， $1 \leq c_{i} \leq 10$ ， $1 \leq l_{i} \leq L$ ， $1 \leq v_{i} \leq 100$

输入

输出

答案