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