P1759 Diving to the Heavens

Direct-to-Heaven Road: Xiao A’s Adventure, Part III.

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

三个数 $m, v, n$ 如题目所说。 接下来 $n$ 行，每行三个数 $a_i, b_i, c_i$ 分别表示所含的重力，阻力，能够支撑的时间。

On the first line, print one integer: the maximum total time. On the next line, print the indices of the chosen items. Items are numbered from $1$ to $n$ in input order. If multiple optimal solutions exist, output the lexicographically smallest one by item indices. Print the indices in increasing order, separated by single spaces.

Constraints: For $100\%$ of the testdata, $1 \le m, v \le 200$, $1 \le n \le 100$. It is guaranteed that there exists at least one feasible solution. Translated by ChatGPT 5