Монстры
Вы - главный рекрутер в корпорации 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-го теста.