Monsters
You're chief hiring officer in Monsters Inc. You need to handle a new project which will run for N days. On i-th day, you need a minimum of X_i monsters for the project to be successful. Based on market analysis, you have gathered a compensation table, which tells you the cost of hiring a monster on the beginning of day i and relieving him of duty at the end of day j for all pairs (i,j). Note that you need to relieve all the monsters which still remain at the end of N th day.
You want to estimate the minimum possible cost which you'll incur in running the project.
Input
The first line of the input contains T, the number of test cases. For each test case, the first line contains N, the number of days for which the project will run. Next line contains N numbers, i-th integer denoting the minimum number of employees required on day i. Next N lines contain the cost table. i-th line contains (N - i + 1) numbers, denoting the cost of hiring a monster on the beginning of day i and relieving him at the end of day i, i + 1, ..., N; respectively. Test cases will be separated by a blank line.
It is known that 1 ≤ T ≤ 10, 1 ≤ N ≤ 100, 1 ≤ X_i ≤ 100000, 1 ≤ cost[i][j] ≤ 100000.
Output
The output contains T lines, i-th line denoting the minimum possible cost for i-th test case.