Ævintýraröð

이미지 출처: commons.wikimedia.org

Jörmunrekur는 자신이 예전에 가장 좋아했던 DeceitfulLOAM이라는 비디오 게임을 살펴보다가, 이 게임이 고대 역사로 여겨질 뿐만 아니라 자신이 플레이한 뒤로 새로운 버전이 세 개나 나왔으며, 그중 두 개도 마찬가지로 고대로 여겨지고, 하나는 심지어 죽음에서 되살아나기까지 했다는 사실을 알게 되었다! 그는 새로운 버전으로 넘어갈 때 어느 정도의 변화는 받아들이겠지만, 모든 일에는 한계가 있다. 그는 DeceitfulLOAM의 다음 버전인 Glyphplane Classic을 플레이하기로 한다. 변경 사항을 조금 읽어 본 그는 이 버전에는 완료하면 플레이어의 경험치를 증가시키는 다양한 퀘스트가 추가되었다는 사실을 알게 된다. 이를 알게 되자 그의 머릿속에서 계산이 돌아가기 시작한다.

보상은 플레이어의 현재 경험치에 따라 조정된다. 더 구체적으로, 각 퀘스트에는 $a$와 $b$라는 값이 있으며, 플레이어가 현재 경험치를 $x$만큼 가지고 있다면 퀘스트 보상으로 경험치를 $ax + b$만큼 더 얻는다. 이는 퀘스트를 마친 뒤 경험치를 $x + ax + b$만큼 가지게 된다는 뜻이다. 당연히 Jörmunrekur는 이 값을 가능한 한 효율적으로 늘리고 싶다. 그렇다면 퀘스트를 어떤 순서로 완료해야 하는가?

채점

그룹 | 점수 | 제한 조건

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$

입력의 첫 번째 줄에는 퀘스트의 수와 Jörmunrekur의 초기 경험치를 나타내는 두 정수 $n$와 $x$가 주어지며, $0 \leq x \leq 1\,000$이다. 다음 $n$개의 줄에는 각각 하나의 퀘스트에 대한 설명이 주어진다. 각 줄은 퀘스트의 이름으로 시작하고, 그 뒤에 $a$와 $b$의 값이 주어지며, $0 \leq a, b \leq 1\,000$이다. 모든 항목은 공백으로 구분된다. 이름은 영문 대문자와 소문자로만 이루어지며 길이는 최대 $20$자이다. 입력에 주어지는 모든 이름의 길이의 합은 최대 $300\,000$이다. 모든 퀘스트의 이름은 서로 다르다.

Jörmunrekur가 퀘스트를 완료해야 하는 순서대로 퀘스트의 이름을 출력한다. 즉, 가장 먼저 완료해야 하는 퀘스트의 이름을 가장 먼저 출력해야 한다. 각 이름을 한 줄에 하나씩 출력한다. 올바른 답이 여러 개라면 그중 아무거나 하나를 출력해도 된다.