You Are Fired!

펌프 조직(Pump Organization)의 최근 분기 보고서는 전혀 희망적이지 않다. 비용은 폭증한 반면 매출은 42% 감소했다. 수치를 자세히 살펴본 CEO 대고베르트 J. 펌프는 회사를 구할 유일한 방법이 직원 일부를 해고하는 것이라고 결론 내린다.

문제는 CEO 펌프가 최근 인터뷰에서 "자신은 하나님이 창조한 최고의 일자리 창출자"라고 주장했다는 점이다. 따라서 그가 너무 많은 사람을 해고하면, 부정하고 부패한 좌파 언론이 분명히 이를 보도할 것이고, 그러면 그는 극도로 신뢰할 수 없는 사람처럼 보일 것이다. 펌프 조직의 PR 전문가들은 이미 CEO 펌프가 언론의 주목을 끌지 않고 해고할 수 있는 직원 수를 추정해 두었다. 만일을 대비해 CEO 펌프는 해고하는 직원 수를 가능한 한 적게 하기로 한다.

회사의 모든 직원 명단과 각자의 급여를 가지고, CEO 펌프는 k명 이하의 직원을 해고해 최소 d달러를 절약해야 한다. 이것이 가능하다면, CEO 펌프는 그들 각자에게 직접 말하고 싶어 한다. YOU ARE FIRED!

입력은 다음과 같이 주어진다.

• 세 정수 n, d, k가 있는 한 줄

  • n (1 ≤ n ≤ 10 000)은 펌프 조직의 직원 수이다.
  • d (1 ≤ d ≤ 109)는 CEO 펌프가 최소한 절약해야 하는 금액이다.
  • k (1 ≤ k ≤ n)는 CEO 펌프가 언론의 주목을 끌지 않고 해고할 수 있는 최대 직원 수이다.

• n개의 줄. 각 줄에는 문자열 si와 정수 ci가 있다.

  • si (1 ≤ |si| ≤ 7)는 i번째 직원의 이름이다.
  • ci (1 ≤ ci ≤ 100 000)는 i번째 직원의 급여이다.

모든 si는 서로 다르며, 영문 알파벳 대소문자만 포함한다.

k명 이하의 직원을 해고해 최소 d달러를 절약할 방법이 없으면 impossible을 출력한다.

k명 이하의 직원을 해고해 최소 d달러를 절약할 방법이 있으면, 출력은 다음과 같다.

• 해고할 사람의 수 x (1 ≤ x ≤ k)를 나타내는 정수 하나가 있는 한 줄.
• x개의 줄. 각 줄에는 해고할 i번째 직원의 이름 si와 YOU ARE FIRED!가 있다.

여러 해가 있으면 어느 것이든 허용된다.