Monsters#1175
You are the chief hiring officer at Monsters Inc. You need to run a new project for days. On the -th day, the project requires at least X_i monsters to work. Based on market analysis, you have prepared a cost table. For every pair , the table gives the cost of hiring a monster at the beginning of day and releasing it at the end of day . Note that at the end of the -th day, all remaining monsters must be released.
The first line contains , the number of test cases. Each test case begins with a line containing , the number of days the project lasts. The following line contains numbers, where the -th number is the minimum number of monsters required on the -th day. The next lines describe the cost table: the -th line contains (N - i + 1) numbers, each representing the cost of hiring a monster at the beginning of day and releasing it at the end of days i, i+1, \ldots, N, respectively. Test cases are separated by a blank line.
It is guaranteed that 1 \leq T \leq 10, 1 \leq N \leq 100, 1 \leq X_i \leq 100000, 1 \leq \text{cost}_{ij} \leq 100000.
Output lines; the -th line should contain the minimum possible cost for the -th test case.
Example 1