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