Description

Yume really likes the artwork of the reward card for this event, so he decides to grind this event to get the reward. The rules of this event are special: before the event’s end time, the player must finish all designated songs (each song can be played only once) and reach a certain score to claim the reward. If the player does not finish all the songs in time, or the score is below the threshold, the reward cannot be claimed. Each song has a limited reward open window. If the player finishes the song within this window, they earn a score (score earned = open window time − current total time used). If the song is completed after this window, no score is earned.

This should have been easy for a veteran like Yume, but he mistakenly remembered the event end time as the start time. When he logged in, he was shocked to find that the event was about to end. Now he wants to know whether, within the remaining time, he can finish all the songs and reach the score threshold to get the event card. To save time, he asks you to solve this problem. Based on the given data, determine whether he can achieve the goal in the remaining time. If he can, tell him the order in which to complete the songs.

Input Format

The first line contains three integers $n,m,t$, representing the number of required songs, the minimum score needed to obtain the reward, and the remaining time until the event ends.

The next $n$ lines each contain a string $S_i$ and two integers $T_i$ and $M_i$, indicating that the $i$-th song’s name is $S_i$, completing the $i$-th song takes $T_i$ time, and the $i$-th song’s reward open window has $M_i$ time remaining. It is guaranteed that $T_i \le M_i$. The input data are given in the lexicographic order of $S_i$.

Output Format

If Yume can achieve the goal and claim the reward before the event ends, output an integer $C$ on the first line, representing the maximum score that can be obtained while still getting the reward.

Then output $n$ lines, listing the song names in the order they are completed. If there are multiple valid orders, output the lexicographically smallest one.

If Yume cannot finish all the songs before the event ends, output No Answer.

3 2 10
BokutachiwaHitotsunoHikari 3 8
Korekara 1 2
SnowHalation 2 5

6
SnowHalation
BokutachiwaHitotsunoHikari
Korekara

2 1 2
AoizoraJumpingHeart 1 2
TimeLapse 2 4

No Answer

Hint

• For $0\%$ of the testdata, it is identical to the testdata.
• For $20\%$ of the testdata, $n \le 5$.
• For $40\%$ of the testdata, $n \le 9$.
• For $70\%$ of the testdata, $n \le 15$.
• Additionally, for $10\%$ of the testdata, $\sum\limits_{i=1}^{n} T_i < t$.
• For $100\%$ of the testdata, $n \le 22$, the length of $S_i$ does not exceed $50$. It is guaranteed that $m, t, M_i, T_i$ and any of their sums are within the maximum range of int.

Translated by ChatGPT 5