Optimal Playlist Generation

You are given a list of songs where each song is represented by a tuple ( (id, rating, duration) ). The objective is to select a subset of songs such that the total rating is maximized without exceeding a maximum allowed duration ( D ). In the event of a tie in total rating, choose the subset with the minimum total duration. Finally, output the sorted song IDs of the selected subset. If no valid playlist can be constructed, output an empty list.

inputFormat

The first line contains two integers ( n ) and ( D ) where ( n ) is the number of songs and ( D ) is the maximum allowed duration. Each of the following ( n ) lines contains three integers: the song id, the rating, and the duration of the song.

outputFormat

Output a single line containing the selected song IDs in increasing order, separated by spaces. If no songs are selected, output an empty line.## sample

4 90
1 10 60
2 15 35
3 10 40
4 5 25

2 3