Problem M
Ævintýraröð
Languages
en
is
Jörmunrekur was looking into his old favourite video game called DeceitfulLOAM and discovered that not only was it considered ancient history, but there had been three new versions of it since he played it, two of which are also considered ancient as well, and one of which had even risen from the dead! He will accept some changes when moving up to new versions, but there are limits to everything. He decides to play the version that comes after DeceitfulLOAM, known as Glyphplane Classic. He reads a bit about the changes and finds out that in this version various quests have been added which increase a player’s experience points upon completion. Learning this makes his mind start grinding away.
The rewards scale with the player’s current experience points. More specifically, each quest has some values $a$ and $b$ such that if the player currently has $x$ experience points, the quest reward will be $ax + b$ more experience points. This means they have $x + ax + b$ experience points after the quest. Naturally, Jörmunrekur wants to increase these values as efficiently as possible, so in what order should he complete the quests?
Input
The first line of input contains two integers $n$ and $x$, the number of quests and Jörmunrekur’s initial number of experience points, where $0 \leq x \leq 1\, 000$. Next there are $n$ lines, each describing one quest. Each line starts with the name of the quest, followed by its values of $a$ and $b$, where $0 \leq a, b \leq 1\, 000$, all separated by spaces. The names only contain English upper and lower case letters and are at most $20$ characters in length. The total length of all names in the input is at most $300\, 000$. All quests have different names.
Output
Print the names of the quests in the order Jörmunrekur should finish them, meaning the quest he should complete first should be printed first. Print each name on its own line. If there are multiple correct answers, you may print any one of them.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$1 \leq n \leq 2$ |
|
2 |
20 |
$1 \leq n \leq 8$ |
|
3 |
20 |
$1 \leq n \leq 50$ |
|
4 |
20 |
$1 \leq n \leq 500$ |
|
5 |
20 |
$1 \leq n \leq 10^5$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
8 0 CooksAssistant 50 250 SheepShearer 25 125 RestlessGhost 62 500 ImpCatcher 100 375 VampireSlayer 150 325 DoricsQuest 75 175 GoblinDiplomacy 15 125 SeaSlug 200 175 |
GoblinDiplomacy RestlessGhost CooksAssistant SheepShearer ImpCatcher DoricsQuest VampireSlayer SeaSlug |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 100 YouGetNothing 0 0 NoScaling 0 100 NoConstant 100 0 |
YouGetNothing NoScaling NoConstant |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 1 A 1 4 B 2 9 |
B A |
