Масове виробництво

Star Fleet має розгорнути ескадру кораблів на краю простору Федерації. Є сусідня планета, де можна побудувати кораблі, але на планеті немає інфраструктури для підтримки будівництва кораблів з нуля. Однак можливо зібрати кораблі, використовуючи попередньо виготовлені комплекти, що містять набір базових частин. Кожен комплект призначений для перетворення в корабель шляхом перетворення базових частин у необхідні компоненти корабля. Щоб забезпечити послідовність у будівництві, частини з різних комплектів не повинні змішуватися; кожен комплект має бути використаний повністю для побудови рівно одного корабля. Ця ескадра складається з двох різних класів кораблів: кораблі класу A та кораблі класу B. Обидва класи складаються з однакової загальної кількості компонентів, хоча їхній індивідуальний склад різний. Кожна базова частина здатна перетворитися на будь-який тип компонента корабля, хоча вартість перетворення базової частини в компонент корабля варіюється залежно від типу базової частини та типу компонента корабля. Ви відповідаєте за створення цих попередньо виготовлених комплектів, які повинні бути ідентичними один одному. У вас є доступ до M5, найвеличнішого комп'ютера всіх часів.

Яким має бути склад комплекту, щоб мінімізувати загальну вартість будівництва ескадри?

Вхідні дані

Вхідні дані починаються з рядка з одним цілим числом T (1 ≤ T ≤ 50), що позначає кількість тестових випадків. Кожен тестовий випадок починається з рядка з чотирма цілими числами M, N, A та B (1 ≤ M, N ≤ 10, 1 ≤ A, B ≤ 100), де M позначає кількість типів базових частин, N позначає кількість типів компонентів корабля, A позначає кількість кораблів класу A, а B позначає кількість кораблів класу B. Далі йде рядок з N цілими числами a_i, що позначають кількість компонента корабля i, необхідного для кожного корабля класу A (0 ≤ a_i ≤ 100). Далі йде рядок з N цілими числами b_i, що позначають кількість компонента корабля i, необхідного для кожного корабля класу B (0 ≤ b_i ≤ 100, Σ_ia_i = Σ_ib_i). Далі йдуть M рядків з N цілими числами c_ij (0 ≤c_ij ≤ 100), що позначають вартість перетворення однієї базової частини i в один компонент корабля j.

Вихідні дані

Для кожного тестового випадку виведіть рядок з одним цілим числом, що дорівнює мінімальній загальній вартості перетворення для збирання всіх кораблів з фабричних комплектів.

Приклади

Примітка

У наведеному прикладі оптимальний фабричний комплект має одну з кожної базової частини; такий комплект коштує 1 для перетворення в компоненти для корабля класу A і 2 для перетворення в компоненти для корабля класу B.