Valid Playlist Generation

You are given n songs, each defined by a name and a duration (in seconds). Your task is to generate a playlist that meets the following conditions:

• The total duration of the playlist must equal exactly T seconds.
• Each song can be used at most once.
• The playlist must satisfy the repetition constraint: when adding a new song, it must not have been played in the last k songs. In other words, if the current playlist contains at least k songs, the song to be added must not appear among the last k songs already in the playlist.

If it is possible to create such a playlist, print the corresponding song names in order (separated by a space). Otherwise, print -1.

Formally, if we denote the playlist by a sequence \(p_1, p_2, \dots, p_m\) with \(\sum_{i=1}^{m} d(p_i) = T\) (where \(d(p_i)\) is the duration of the song \(p_i\)), then for any index \(i\) such that \(i > k\), the song \(p_i\) must not be equal to any of \(p_{i-k}, p_{i-k+1}, \dots, p_{i-1}\).

inputFormat

The input is read from stdin and has the following format:

n T k
song1 duration1
song2 duration2
... 
songn durationn

Where n is the number of songs, T is the target total duration, and k is the repetition constraint window. Each of the next n lines contains a song name (a string without spaces) and an integer representing its duration.

outputFormat

Print a single line to stdout. If a valid playlist exists, print the song names in the order they should be played, separated by a space. Otherwise, print -1.

5 300 3
song1 100
song2 150
song3 50
song4 200
song5 100

song1 song2 song3