Монстри
Ви - головний рекрутер у корпорації Monsters Inc. Вам необхідно забезпечити роботу нового проекту протягом N днів. У i-ий день необхідно щоб у проекті працювало як мінімум X_i монстрів. Аналізуючи ринок, ви склали таблицю компенсації, у якій зібрано інформацію про вартість найму монстра на початку i-го дня і звільненні його у кінці j-го дня для всіх пар (i,j). Відмітимо той факт, що ви повинні звільнити всіх монстрів у кінці N-го дня.
Необхідно знайти найменшу вартість проведення проекту.
Вхідні дані
Перший рядок містить кількість тестів T. Перший рядок кожного тесту містить кількість днів N, у період яких буде продовжуватись проект. Наступний рядок містить N чисел, i-е число вказує на мінімальну кількість працівників, які повинні займатись проектом у i-ий день. Наступні N рядків описують таблицю вартостей. i-ий рядок містить (N - i + 1) чисел, які вказують на вартість найму монстра на початку i-го дня і звільненні його у кінці відповідно дня i, i + 1, ..., N. Тестт відокремлені пустим рядком.
Відомо, що 1 ≤ T ≤ 10, 1 ≤ N ≤ 100, 1 ≤ X_i ≤ 100000, 1 ≤ cost[i][j] ≤ 100000.
Вихідні дані
Складаються з T рядків, i-ий рядок містить шукану найменшу вартість проекту для i-го тесту.