Олимпиадный тренинг

Задача . D. Подпоследовательность


У Алисы есть целочисленная последовательность \(a\) длины \(n\) и все ее элементы различны. Она выбирает из \(a\) подпоследовательность длины \(m\) и определяет ценность подпоследовательности \(a_{b_1},a_{b_2},\ldots,a_{b_m}\) как \(\)\sum_{i = 1}^m (m \cdot a_{b_i}) - \sum_{i = 1}^m \sum_{j = 1}^m f(\min(b_i, b_j), \max(b_i, b_j)),\(\) где \(f(i, j)\) обозначает \(\min(a_i, a_{i + 1}, \ldots, a_j)\).

Алиса хочет, чтобы вы помогли ей максимизировать ценность выбираемой подпоследовательности.

Последовательность \(s\) является подпоследовательностью \(t\), если \(s\) может быть получена из \(t\) удалением нескольких (возможно, ни одного или всех) элементов.

Входные данные

Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \le m \le n \le 4000\)).

Во второй строке записано \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i < 2^{31}\)).

Выходные данные

Выведите максимальное значение, которое может получить Алиса.

Примечание

В первом примере Алиса может выбрать подпоследовательность \([15, 2, 18, 13]\), которая имеет ценность \(4 \cdot (15 + 2 + 18 + 13) - (15 + 2 + 2 + 2) - (2 + 2 + 2 + 2) - (2 + 2 + 18 + 12) - (2 + 2 + 12 + 13) = 100\).

Во втором примере существует множество подпоследовательностей ценности \(176\), одна из них — \([9, 7, 12, 20, 18]\).


Примеры
№Входные данныеВыходные данные
1
6 4
15 2 18 12 13 4
100
2
11 5
9 3 7 1 8 12 10 20 15 18 5
176
3
1 1
114514
0
4
2 1
666 888
0
Статистика успешных решений по компиляторам
 Кол-во
С++4