J — Ki vagy rúgva!

A Pump Szervezet legutóbbi negyedéves jelentése egyáltalán nem tűnik ígéretesnek: a költségek elszabadultak, míg a bevétel 42%-kal csökkent. Miután jobban megnézte a számokat, Dagobert J. Pump vezérigazgató arra a következtetésre jutott, hogy csak úgy mentheti meg a vállalatot, ha elbocsátja néhány alkalmazottját.

A probléma csak az, hogy Pump igazgató nemrég azt állította egy interjúban, hogy „ő a valaha élt legnagyobb munkahelyteremtő”. Ha tehát túl sok embertől válna meg, a becstelen, korrupt baloldali média nyilván beszámolna róla, és ezzel igencsak megbízhatatlannak állítaná be őt. A Pump Szervezet PR-szakemberei már meg is becsülték, hogy Pump igazgató hány dolgozótól szabadulhat meg anélkül, hogy felkeltené a média érdeklődését. A biztonság kedvéért Pump igazgató úgy döntött, hogy a lehető legkevesebb alkalmazottat rúgja ki.

Figyelembe véve a vállalat összes dolgozóját és a fizetésüket, Pump igazgatónak legalább d dollárt kell megtakarítania legfeljebb k alkalmazott elbocsátásával. Ha ez megvalósítható, Pump igazgató mindegyikükkel személyesen szeretné közölni: KI VAN RÚGVA!

A bemenet specifikációja

A bemenet az alábbiakból tevődik össze:

egy sor az n, d és k egész számokkal, ahol
- n (1 ≤ n ≤ 10 000) a Pump Szervezet alkalmazottainak száma;
- d (1 ≤ d ≤ 10⁹) az az összeg, amennyit Pump igazgatónak minimálisan meg kell takarítania;
- k (1 ≤ k ≤ n) azon dolgozók maximális száma, akiktől Pump igazgató megválhat anélkül, hogy felkeltené a média érdeklődését;
n sor, amelyek mindegyike egy s_i sztringet és egy c_i egész számot tartalmaz, ahol
- s_i (1 ≤ |s_i| ≤ 7) az i-edik dolgozó neve;
- c_i (1 ≤ c_i ≤ 100 000) az i-edik dolgozó fizetése.

Mindegyik s_i különböző, és csak az angol ábécé kis- és nagybetűit tartalmazza.

A kimenet specifikációja

Ha nincs mód arra, hogy megtakarítsunk legalább d dollárt legfeljebb k alkalmazott kirúgásával, akkor az „impossible” szót kell a kimenetre írni.

Ha van mód arra, hogy megtakarítsunk legalább d dollárt legfeljebb k alkalmazott kirúgásával, akkor a kimenetet az alábbiak szerint kell összeállítani:

egy sor, amely egyetlen x egész számot tartalmaz (1 ≤ x ≤ k), ahol x az elbocsátandó emberek száma;
x sor, mindegyik az „s_i, YOU ARE FIRED!” szöveggel, ahol s_i az i-edik elbocsátandó alkalmazott neve.