N. Самое неудачное дерево поиска

3000 мс · 256 МБ · всё или ничего

Как классная задача про оптимальное дерево поиска, но найти надо наибольшую стоимость - то есть самое неудачное дерево.

Динамика та же, минимум меняется на максимум:

dp[i][j] = \max_{i \le k \le j} \Bigl( dp[i][k-1] + dp[k+1][j] + \sum_{t=i}^{j} f_t - f_k \Bigr)

Полезно посмотреть, какое дерево получается: у худшего дерева корень обычно на краю отрезка, и оно вырождается в цепочку. Это ровно то, чего избегают сбалансированные деревья поиска.

Обратите внимание, что оптимизация Кнута здесь неприменима: неравенство четырёхугольника даёт монотонность точки минимума, а не максимума. Если вы её всё-таки написали и ответы сошлись на случайных тестах - это ничего не доказывает, поищите контрпример.

Формат тот же: несколько тестов, по одному в строке, читать до конца файла.

Формат ввода

Каждая строка - отдельный тест: число $n$ ( $1 \le n \le 250$ ), затем $n$ частот ( $0 \le f_i \le 100$ ).

Сумма $n$ по всем тестам не превосходит 5000.

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

Для каждого теста выведите наибольшую стоимость дерева поиска.

Примеры

ввод

1 5
3 10 10 10
3 5 10 20

вывод

0
30
50

ввод

1 0

вывод

Войдите, чтобы отправлять решения.