401848: GYM100541 G Production Planning

G. Production Planningtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

LazyCorp is preparing its production plan for a big interplanetary sporting event to be held in planet Alpha. LazyCorp is capable of manufacturing n types of products that require n - 1 types of materials. Anticipating the huge demand from the sporting event, LazyCorp has stocked the required materials for production. Currently, the company has b_i material of type i(i = 1, 2, ..., n−1). Based on previous years statistics, LazyCorp has identified the consumption rate of each material type for production. The consumption rate is captured by a coefficient matrix A = (a_ij: i = 1, 2, …, n−1;j = 1, 2, …, n), where a_ij is the amount of type i material needed to manufacture one product of type j. We can assume that the rank of A is n - 1. Based on market study and forecast, LazyCorp has also figured out the expected profit from one unit of type j product to be c_j, j = 1, 2, …, n. A production plan of the company can be represented by a vector (x₁, x₂, …, x_n) where x_j is a non-negative integer indicating the quantity of type j product to be manufactured, j = 1, 2, …, n.

LazyCorp board of directors is interested in working out if they can have a production plan that use up all n−1 types of materials in stock (i.e., the amount of type i material to be used in the production plan has to be exactly b_i, i = 1, 2, …, n−1). In case there exists such a production plan, they are interested in identifying the production plan that would bring the maximum expected profit.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 20. The following lines describe the datasets.

• The first line contains an integer n (n ≤ 200), which is the number of product types.
• The second line contains n positive integers c₁, c₂, …, c_n (c_j ≤ 1000,  j = 1, 2, …, n);
• The third line contains n−1 positive integers b₁, b₂, …, b_n - 1 (b_i ≤ 10⁶,  i = 1, 2, …, n−1);
• The u_th line in the next n−1 line contains n positive integers, each not exceeding 10⁶, a_u1, a_u2, …, a_un; u = 1, 2, …, n−1.

Two consecutive numbers on the same line are separated by a space.Output

For each dataset, write on a single line an integer that is the expected profit of the found production plan or  - 1 in case there is no such production plan.

ExamplesInput

2
3
1 2 3
20 100
1 1 1
2 3 5
2
1 5
100
3 12

Output

60
-1