Массовое производство

Звездный флот должен развернуть эскадрилью кораблей на краю пространства Федерации. На близлежащей планете можно построить корабли, но там отсутствует инфраструктура для их создания с нуля. Однако возможно собрать корабли, используя заранее подготовленные комплекты, содержащие набор базовых частей. Каждый комплект предназначен для превращения в корабль путем преобразования базовых частей в необходимые компоненты. Чтобы обеспечить последовательность в строительстве, части из разных комплектов не должны смешиваться; каждый комплект должен быть использован полностью для строительства ровно одного корабля. Эскадрилья состоит из двух различных классов кораблей: класса 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.