Ви - головний рекрутер у корпорації Monsters Inc. Вам необхідно забезпечити роботу нового проекту протягом \textbf{N} днів. У \textbf{i}-ий день необхідно щоб у проекті працювало як мінімум \textbf{X_i} монстрів. Аналізуючи ринок, ви склали таблицю компенсації, у якій зібрано інформацію про вартість найму монстра на початку \textbf{i}-го дня і звільненні його у кінці \textbf{j}-го дня для всіх пар (\textbf{i},\textbf{j}). Відмітимо той факт, що ви повинні звільнити всіх монстрів у кінці \textbf{N}-го дня. Необхідно знайти найменшу вартість проведення проекту. \InputFile Перший рядок містить кількість тестів \textbf{T}. Перший рядок кожного тесту містить кількість днів \textbf{N}, у період яких буде продовжуватись проект. Наступний рядок містить \textbf{N} чисел, \textbf{i}-е число вказує на мінімальну кількість працівників, які повинні займатись проектом у \textbf{i}-ий день. Наступні \textbf{N} рядків описують таблицю вартостей. \textbf{i}-ий рядок містить (\textbf{N} - \textbf{i} + 1) чисел, які вказують на вартість найму монстра на початку \textbf{i}-го дня і звільненні його у кінці відповідно дня \textbf{i},\textbf{ i} + \textbf{1}, ..., \textbf{N}. Тестт відокремлені пустим рядком. Відомо, що \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 Складаються з \textbf{T} рядків, \textbf{i}-ий рядок містить шукану найменшу вартість проекту для \textbf{i}-го тесту.