luogu#P1759. 通天之潜水

通天之潜水

题目背景

直达通天路·小 A 历险记第三篇

题目描述

在猴王的帮助下,小 A 终于走出了这篇荒山,却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船,但好在小 A 有 nn 个潜水工具。由于他还要背重重的背包,所以他只能背 mm 重的工具,又因为他的力气并不是无限的,河却很宽,所以他只能背有 vv 阻力的工具。但是这条河下有非常重要的数据,所以他希望能够停留的时间最久。于是他找到了你,让你告诉他方案。

输入格式

三个数 m,v,nm, v, n 如题目所说。

接下来 nn 行,每行三个数 ai,bi,cia_i, b_i, c_i 分别表示所含的重力,阻力,能够支撑的时间。

输出格式

第一行一个数,表示最长的时间。

接下来一行,若干个数,表示所选的物品。

100 100 3
50 60 289
40 10 116
50 50 106

405 
1 2

提示

对于 100%100 \% 的数据,1m,v2001 \le m, v \le 2001n1001 \le n \le 100

数据保证一定有方案。

若有多种方案,输出前面尽量小的方案。