은하 간 경매

오늘 은하 간 조약돌 화폐 위원회(ICPC)는 뉴트로늄 카오스 조약돌 화폐(NCPC)의 은하 간 경매를 열었다. 고대 화폐 제조기(ACM)에서 주조된 이 화폐는 우주를 지배하는 열쇠라고 한다.

경매는 매우 치열했고, 사용된 은하 간 화폐의 특이한 구조(필멸자가 이해하기에는 너무 앞서 있다) 때문에 다음 규칙에 따라 진행되었다.

1. 한 번에 한 참가자만 입찰할 수 있었다.
2. 각 참가자는 한 번만 입찰할 수 있었다.
3. 입찰하는 참가자는 그 시점의 최고 입찰가의 두 배 이상을 입찰해야 했다.

처음 입찰하는 참가자는 임의의 양수를 입찰할 수 있었다.

경매가 끝난 뒤에는 패배자가 많았다. 세계 정복의 기회를 방금 잃었으니 당연하다. ICPC는 패배자를 조금이나마 달래고 폭동을 막기 위해 참가자를 대상으로 추첨을 열기로 했다. 추첨의 당첨자는 다음과 같이 정한다. ICPC가 임의의 수 s를 고른다. 참가자들의 한 무리가 winning group이라는 것은, 그들이 경매에서 입찰한 금액의 합이 s와 같은 경우를 말한다. 어떤 참가자가 어떤 winning group에 속하면 그 참가자는 추첨에 당첨되어 반짝이는 조약돌 화폐를 상품으로 받는다.

참가자의 이름, 그들이 입찰한 금액, ICPC가 고른 임의의 수 s가 주어질 때, 누가 추첨에 당첨되었는지 구하는 프로그램을 작성하시오.

첫째 줄에는 두 정수 n과 s가 주어진다. n은 참가자의 수이고 1 ≤ n ≤ 1 000이며, s는 ICPC가 고른 임의의 수이고 1 ≤ s < 10^1000이다.

다음 n개 줄에는 참가자를 나타내는 정보가 주어진다. 각 줄에는 문자열 t와 정수 b가 주어진다. t는 참가자의 이름이고, b는 그가 입찰한 금액이며 1 ≤ b < 10^1000이다. 각 참가자의 이름은 서로 다르고, 영어 알파벳 1자 이상 20자 이하로 이루어진다.

추첨에 당첨된 참가자의 수 k를 출력한다. 그다음 k개 줄에 추첨에 당첨된 참가자의 이름을 한 줄에 하나씩, 순서에 상관없이 출력한다.