描述

鲁拉塔尼亚（Ruratania）刚刚进入资本主义阶段，正在许多领域开展新的创业活动，包括交通运输领域。运输公司 TransRuratania 正在开通一条从城市 A 到城市 B 的新特快列车，途中会在一些车站停靠。车站依次编号，城市 A 的车站编号为 0，城市 B 的车站编号为 $m$。为了提高客运能力，从而增加收入，该公司正在进行一项实验。列车的最大载客量为 $n$ 名乘客。火车票的价格等于起始车站和目的车站之间的车站数量（包括目的车站）。在列车从城市 A 出发之前，会收集沿途所有车站的订票订单。来自车站 $S$ 的订票订单意味着从 $S$ 到某个固定目的车站的所有订票请求。如果由于客运能力的限制，公司无法接受所有订单，其拒绝政策是对于来自单个车站的单个订单，要么完全接受，要么完全拒绝。

输入

输入文件被分成若干块。每块的第一行包含三个整数：列车的载客容量 $n$、城市 B 车站的编号以及来自所有车站的订票订单数量。接下来的行包含订票订单。每个订票订单由三个整数组成：起始车站、目的车站、乘客数量。在一个块中最多可以有 22 个订单。城市 B 车站的编号最多为 7。当第一行的三个数字都为 0 时，表示输入文件结束。

输出

输出文件由与输入文件的块相对应的行组成（不包括终止块）。每一行包含最大可能的总收益。

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

19
34

来源

1995 年中欧