Hide

Problem M
Ævintýraröð

Languages en is
/problems/aevintyrarod/file/statement/en/img-0001.png
Image taken from commons.wikimedia.org

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

Please log in to submit a solution to this problem

Log in