On day 1, a mobile manufacturing company bought L quantities of raw materials which can produce exactly L mobile phones. The raw materials are then transported to factories.

The company owns M factories located at various locations where these raw materials are converted into mobile phones. ith factory is capable of producing at most F[i] mobile phones provided the availability of raw materials.

The manufactured mobile phones can be transported to N shops at various locations where these mobile phones are sold. Each shop has a selling capability. ith shop can sell at most S[i] mobile phones in a day. You are given a 2D map of order MxN. ith factory can transport at most map[i][j] mobile phones to jth shop.

Find the maximum number of mobile phones that can be sold by the company on day 1. For simplicity you can assume that the time taken for transportation of raw materials and mobiles as 0.

Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of 3 integers L, M and N. The next line consists of M integers representing the array F. The next line consists of N integers representing the array S. The next M lines represent the map.

Output

For each test case, find the maximum number of mobile phones that can be sold by the company on day 1.

Constraints

1 <= t <= 100

1 <= L <= 1000

1 <= M <= 200

1 <= N <= 200

0 <= F[i] <= 1000

0 <= S[i] <= 1000

0 <= map[i][j] <= 1000

Sample

Input
2
5 2 2
3 5
2 3
1 2
1 0
3 3 1
3 4 4
4
1
2
2

Output
4
3

See Also: Mobile Company 1