Mass Production

Star Fleet needs to deploy a squadron of ships at the edge of Federation space. Ships can be built on a nearby planet, but that planet has no facilities for building a ship from scratch. Prefabricated kits holding an assortment of base parts can be shipped there instead, and the ships are assembled from those kits.

A kit turns into a ship when its base parts are converted into the ship components the ship needs. Parts from different kits must not be mixed, so each kit is used in its entirety to build exactly one ship.

The squadron has two classes of ships, Class A and Class B. Both classes need the same total number of ship components, but the mix of components differs. Any base part can be turned into any type of ship component, and the conversion cost depends on the base part type and the ship component type.

You design the kits, and every kit must be identical. You also have M5, the greatest computer of all time. What should the kit contain so that the total conversion cost of building the whole squadron is as small as possible?

The first line contains an integer $T$ ($1 \le T \le 50$), the number of test cases.

Each test case begins with a line containing four integers $M$, $N$, $A$, and $B$ ($1 \le M, N \le 10$; $1 \le A, B \le 100$), where $M$ is the number of base part types, $N$ is the number of ship component types, $A$ is the number of Class A ships required, and $B$ is the number of Class B ships required.

The next line contains $N$ integers $a_i$ ($0 \le a_i \le 100$), where $a_i$ is the quantity of ship component $i$ needed for one Class A ship.

The next line contains $N$ integers $b_i$ ($0 \le b_i \le 100$, $\sum a_i = \sum b_i$), where $b_i$ is the quantity of ship component $i$ needed for one Class B ship.

Each of the next $M$ lines contains $N$ integers $c_{ij}$ ($0 \le c_{ij} \le 100$), the cost of converting a single base part $i$ into a single ship component $j$.

For each test case, print one line with a single integer, the minimum total conversion cost of assembling every ship of the squadron from the kits.

In the example, the best kit holds one base part of each type. Converting that kit into the components of a Class A ship costs 1, and converting it into the components of a Class B ship costs 2.