Bütün kompyuter oyunlarının layihələndiriciləri öz proqramlarını daha ağıllı və təbii etmək üçün süni intellekt anlayışından istifadə edirlər. Yeni strateji Fövqəltəbii İdentik (Fİ) oyunların layihələndiriciləri öz oyunlarını, xüsusilə kompyuter oyunçularını layihələndirərkən oxşar problemlə rastlaşırlar. Bu oyunlarda hər bir oyunçu (kompyuter və ya insan - oyunçu) hər hansı qızıl, ağac, faydalı qazıntı kimi resurslara malik olur. Oyunçu istənilən vaxt bu resursları nə vaxt, harada sərf etməyi həll edir. Sadəlik üçün fərz edək ki, Sİ-nin bir tip resursu, başqa sözlə qızılı var. Onların xərclənməsi üçün ən əsas sferalardan biri hərbi sahədir. Fİ-lərdə bəzi hərbi vahidlərə oxşar şəkildə qurulmuşları da var. Hər tip onunla bağlı qiymətə, ərzağa və gücə malikdir. Oyunçu müəyyən vahid almaq istəyirsə, o verilmiş yeni əsgər tipi ilə müəyyənləşən zəruri məbləğdə pula malik olmalı, həmçinin istehsalat üçün zəruri miqdarda ərzaqla kömək etməlidir. Əgər o bir əsgər ala bilirsə, onda onun ordusunun ümumi gücü bu tip əsgərin gücü qədər artır. Fİ layihələndiricisi bu proqramı elə hazırlamaq istəyir ki, yalnız qeyd olunmuş sayda yeni döyüşçü almaq mümkün olsun. Tapşırıq ondan ibarətdir ki, konkret məbləğdə pul, ərzaq və qeyd olunmuş seçim sayına malik olduqda öz hərbi gücünü maksimum edən belə kompyuter oyunçusunu proqramlaşdıran Fİ layihələndiricisinə kömək edin. Məsələn, biz \textbf{300} vahid qızıla malikiksə, bizim ərzaq ehtiyatımız \textbf{20}, seçim vahidinin sayı \textbf{3} olur. Onda biz düz \textbf{3} vahid belə yeni əsgər almalıyıq ki, onları saxlamaq üçün \textbf{20} vahiddən çox olmayan material zəruridir və onların ümumi qiyməti \textbf{300}-ü aşmamalıdır, tam güc isə (əsgərlərin cəmi gücü) maksimum olmalıdır. Qeyd edək ki, bir tip əsgər bir dəfədən çox seçilə bilər. \InputFile Birinci sətirdə yeganə tam ədəd - test hallarının sayı yerləşir. Sonra hər test halları üçün məlumatlar gəlir. Hər bir test halı dörd tam ədəd yerləşən bir sətirlə başlayır. Birinci ədəd \textbf{М (0 ≤ М ≤ 5000)} - cari əlçatan qızıl (pul), ikinci ədəd \textbf{F (0 ≤ F ≤ 500)} verilmiş anda əlçatan ərzaq ehtiyatı, üçüncü ədəd \textbf{U} - dəqiq alınacaq yeni əsgər seçimlərinin sayı və dördüncü ədəd \textbf{T (1 ≤ U, T ≤ 10)} - əlçatan yeni əsgər tiplərinin sayı verilir. Sonrakı T sayda sətirdə hər tip üçün bir sətir olmaqla yeni əsgər tipləri üçün məlumatlar yerləşir. Bu sətirlərin hər birində üç ədəd yerləşir: yeni əsgərlərin sayı (\textbf{1}-dən \textbf{100}-dək), zəruri olan ərzağın sayı (\textbf{1}-dən \textbf{20}-dək) və yeni əsgərlərin gücü(mənfi olmayan tam ədəd). Fərz edilir ki, iki eyni tipli yeni əsgər yoxdur. \OutputFile Yeganə sətirdə hər bir test halı üçün verilmiş strategiyanın icrası nəticəsində almaq mümkün olan maksimum gücü göstərən tam ədəd və ya verilmiş sayda pul və ərzaq toplusunda gücü artırmaq mümkün olmadıqda "impossible" sözü .