Архивист

Описание задачи

На архивном сервере на орбите Земли расположены $N$ модулей, выстроенных в ряд. Каждый модуль содержит неизвестное целое значение: $p_1, p_2, \ldots, p_N$.

Хусанбой хочет узнать все эти значения, но из-за системы безопасности он не может напрямую прочитать содержимое модулей. Сервер предоставляет только следующую платную услугу:

Если Хусанбой выбирает $i$ и $j$ ($1 \le i \le j \le N$), сервер сообщает ему сумму значений в интервале $[i, j]$: $p_i+$. Взамен Хусанбой платит «кредитов».

Husanboy может сделать столько запросов, сколько захочет. Его цель — точно восстановить все значения $p_1, p_2, \ldots, p_N$, минимизируя при этом общую стоимость.

Формат ввода

Первая строка содержит одно положительное целое число $N$.

Следующие $N$ строк описывают стоимость запросов. В строке $i+1$ находится $N-i+1$ неотрицательных целых чисел в следующем порядке: $C(i,i),\ C(i,i+1),\ \ldots,\ C(i,N)$

Ограничения

$1 \le N \le 1000$

$0 \le C(i,j) \le 10^6$ для всех $1 \le i \le j \le N$

Формат вывода

Выведите одно целое число — минимальную общую стоимость, которую Хусанбой должен заплатить, чтобы определить все элементы массива $p$.

Оценка

3
5 5 1
5 2
5

8