대량 생산

우주 함대가 연방 영역의 경계에 함선 편대를 배치하려고 한다. 근처 행성에서 함선을 만들 수는 있지만, 그 행성에는 함선을 처음부터 건조할 설비가 없다. 대신 여러 종류의 기본 부품을 담은 조립 키트를 보내면 현지에서 함선을 조립할 수 있다.

키트 하나는 그 안의 기본 부품을 함선 부품으로 변환해서 함선 한 척이 된다. 조립 품질을 일정하게 유지하려면 서로 다른 키트의 부품을 섞어 쓰면 안 된다. 즉, 키트 하나는 남김없이 다 써서 정확히 함선 한 척을 만든다.

편대는 A급 함선과 B급 함선으로 이루어진다. 두 등급은 필요한 함선 부품의 총 개수가 같지만, 부품별 구성은 서로 다르다. 기본 부품은 어떤 종류의 함선 부품으로도 변환할 수 있고, 변환 비용은 기본 부품의 종류와 함선 부품의 종류에 따라 정해진다.

조립 키트 설계는 당신이 맡았고, 키트는 모두 똑같아야 한다. 역사상 가장 뛰어난 컴퓨터 M5도 쓸 수 있다. 편대 전체를 건조하는 변환 비용의 합을 최소로 만들려면 키트를 어떻게 구성해야 할까?

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 50$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $M$, $N$, $A$, $B$ ($1 \le M, N \le 10$; $1 \le A, B \le 100$)가 주어진다. $M$은 기본 부품의 종류 수, $N$은 함선 부품의 종류 수, $A$는 필요한 A급 함선의 수, $B$는 필요한 B급 함선의 수다.

다음 줄에는 정수 $a_i$가 $N$개 주어진다 ($0 \le a_i \le 100$). $a_i$는 A급 함선 한 척에 필요한 함선 부품 $i$의 개수다.

다음 줄에는 정수 $b_i$가 $N$개 주어진다 ($0 \le b_i \le 100$, $\sum a_i = \sum b_i$). $b_i$는 B급 함선 한 척에 필요한 함선 부품 $i$의 개수다.

이어지는 $M$개의 줄에는 각각 정수 $c_{ij}$가 $N$개 주어진다 ($0 \le c_{ij} \le 100$). $c_{ij}$는 기본 부품 $i$ 하나를 함선 부품 $j$ 하나로 변환하는 비용이다.

각 테스트 케이스마다 키트로 편대의 함선을 모두 조립할 때 드는 변환 비용 합의 최솟값을 정수 하나로 한 줄에 출력한다.

예제에서 최적인 키트는 기본 부품을 종류마다 하나씩 담은 키트다. 이 키트를 A급 함선의 부품으로 변환하는 비용은 1, B급 함선의 부품으로 변환하는 비용은 2다.