Closest Playlist

You are given a list of song durations and a target duration \(T\). Your task is to choose a subset of songs such that their total duration is as close as possible to \(T\) without exceeding it.

If no combination of songs has a total duration \(\le T\) (other than the empty set), output an empty line.

Note that each song can be picked at most once and the order in the output should follow the input order.

inputFormat

The first line contains an integer \(n\) representing the number of songs. The second line contains \(n\) space-separated integers representing the durations of the songs. The third line contains a single integer \(T\), the target duration.

outputFormat

Print a single line containing the chosen song durations in order separated by a single space. If no valid subset is found, print an empty line.

4
300 180 200 150
450

300 150