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. All the factories are capable of producing any number of 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. If map[i][j] is 'Y', ith factory can transport its 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 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 <= S[i] <= 1000

map[i][j] ∈ {'Y', 'N'}

Example

Input:
1
10 2 3
5 4 3
YNY
NNY

Output:
8

See Also : Mobile Company 2