Background

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

Output Format

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.

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

405 
1 2

Hint

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