#P18477. Ticket to Ride
Ticket to Ride
Ticket to Ride
《铁路环游》(Ticket to Ride)是一款以铁路为主题的德式桌游。玩家收集并打出火车卡,在地图上修建铁路。修建路线的长度,以及是否连通了抽取的车票卡所指定的远方城市,决定玩家获得的分数。

原照片由 BoardGameGeek 用户 @garyjames 拍摄。
考虑这个游戏的一维版本。有 座城市排成一行,从左到右编号为 。对于每个 ,你可以在城市 与城市 之间放置一条铁路,使这两座城市连通。
有 张车票卡,奖励玩家连通城市的行为。第 张卡由三个整数 表示:如果城市 与城市 通过铁路连通,也就是说,对于每个 ,城市 与城市 之间都放置了铁路,那么你将获得 分。
对于每个 ,求恰好放置 条铁路时可以获得的最大分数。如果没有获得任何奖励,得分为 。
输入格式
输入包含多组测试数据。第一行是整数 ,表示测试数据组数。对于每组测试数据:
第一行包含两个整数 (),分别表示最多可以放置的铁路数量和奖励用的车票卡数量。
接下来 行,第 行包含三个整数 (,),表示城市 与城市 连通时,该卡奖励 分。
保证所有测试数据的 之和不超过 ,所有测试数据的 之和也不超过 。
输出格式
对于每组测试数据,输出一行 个整数,相邻整数之间用一个空格分隔。第 个整数表示恰好放置 条铁路时的最大分数。
不要在行末输出多余空格,否则你的答案可能被认为不正确。
原样例
2
4 3
0 2 3
3 4 2
0 3 1
3 1
1 3 100
2 3 5 6
0 100 100
样例说明
用 表示城市 与城市 之间的铁路。第一组测试数据中:
- 放置 条铁路时,可以放置 ,获得第二张卡的奖励,答案为 。
- 放置 条铁路时,可以放置 与 ,获得第一张卡的奖励,答案为 。
- 放置 条铁路时,可以放置 、 与 ,获得第一、第二张卡的奖励,答案为 。
- 放置全部 条铁路时,可以获得全部奖励,答案为 。