Kütləvi İstehsal

Star Fleet, Federasiya məkanının kənarında bir eskadra yerləşdirməlidir. Yaxınlıqda gəmilərin tikilə biləcəyi bir planet var, lakin planetdə gəmilərin sıfırdan tikintisini dəstəkləyəcək infrastruktur mövcud deyil. Bununla belə, müxtəlif əsas hissələrdən ibarət prefabrik dəstlərdən istifadə edərək gəmiləri yığmaq mümkündür. Hər bir dəst, əsas hissələri lazımi gəmi komponentlərinə çevirərək bir gəmiyə çevrilmək üçün nəzərdə tutulmuşdur. Tikinti ardıcıllığını təmin etmək üçün, müxtəlif dəstlərin hissələri qarışdırılmamalıdır; hər bir dəst tamamilə istifadə olunaraq dəqiq bir gəmi tikilməlidir. Bu eskadra iki fərqli gəmi sinifindən ibarətdir: A sinfi gəmilər və B sinfi gəmilər. Hər iki sinif eyni ümumi komponent sayına malikdir, lakin onların fərdi tərkibi fərqlidir. Hər bir əsas hissə hər hansı bir gəmi komponentinə çevrilə bilər, lakin bir əsas hissəni gəmi komponentinə çevirmə xərci əsas hissə növü və gəmi komponenti növündən asılı olaraq dəyişir. Siz bu prefabrik dəstləri yaratmaqdan məsulsunuz və bütün dəstlər bir-birinə eyni olmalıdır. Siz M5, bütün zamanların ən böyük kompüterinə giriş əldə edirsiniz.

Eskadranın tikinti ümumi xərcini minimuma endirmək üçün dəstin tərkibi necə olmalıdır?

Giriş verilənləri

Giriş bir tam ədəd T (1 ≤ T ≤ 50) ilə başlayır, bu da test hallarının sayını göstərir. Hər bir test halı dörd tam ədəd M, N, A və B (1 ≤ M, N ≤ 10, 1 ≤ A, B ≤ 100) ilə başlayır, burada M əsas hissə növlərinin sayını, N gəmi komponenti növlərinin sayını, A tələb olunan A sinfi gəmilərin sayını və B tələb olunan B sinfi gəmilərin sayını göstərir. Növbəti sətir hər bir A sinfi gəmi üçün lazım olan gəmi komponenti i miqdarını göstərən N tam ədəd a_i ilə davam edir (0 ≤ a_i ≤ 100). Növbəti sətir hər bir B sinfi gəmi üçün lazım olan gəmi komponenti i miqdarını göstərən N tam ədəd b_i ilə davam edir (0 ≤ b_i ≤ 100, Σ_ia_i = Σ_ib_i). Daha sonra M sətir gəlir, hər birində N tam ədəd c_ij (0 ≤c_ij ≤ 100) var, bu da bir əsas hissəni i bir gəmi komponentinə j çevirmə xərcini göstərir.

Çıxış verilənləri

Hər bir test halı üçün, fabrik dəstlərindən bütün gəmiləri yığmağın minimum ümumi çevirmə xərcinə bərabər olan bir tam ədəd ilə bir sətir çıxarın.

Nümunələr

Qeyd

Verilən nümunədə, optimal fabrik dəsti hər bir əsas hissədən birinə malikdir; belə bir dəst A sinfi gəmi komponentlərinə çevirmək üçün 1, B sinfi gəmi komponentlərinə çevirmək üçün isə 2 xərc tələb edir.