eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Монстри

Монстри

Ліміт часу 20 секунд
Ліміт використання пам'яті 64 MiB

Ви - головний рекрутер у корпорації 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. Тестт відокремлені пустим рядком.

Відомо, що 1T10, 1N100, 1X_i100000, 1cost[i][j] ≤ 100000.

Вихідні дані

Складаються з T рядків, i-ий рядок містить шукану найменшу вартість проекту для i-го тесту.

Приклад

Вхідні дані #1
2

1
10
50

2
10 5
500 5
5
Вихідні дані #1
500
50
Автор Аджай Сомані
Джерело Севастопіль - 2010