C. Где моя вода?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Уровень 3 — Дэвид Луис Ортега, Где моя вода?

Пусть $$$n, h$$$ — положительные целые числа. Крокодильчик Свампи нуждается в воде для своей ванны, и ваша задача — доставить ее к нему. Над его домом находится сетка размером $$$h \times n$$$ из грязевых и водяных плиток с $$$n$$$ колонками, пронумерованными $$$1, \ldots, n$$$. В колонке $$$i$$$ нижние $$$a_i$$$ плитки — это грязь, а остальные сверху — водяные плитки.

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

Например, установка дренажа на $$$\times$$$ в сетке ниже позволит откачать как верхние левые, так и верхние правые водяные плитки, и в результате будет откачано $$$10$$$ плиток:

Какое максимальное количество воды вы можете доставить к Свампи после установки не более двух дренажей? Обратите внимание, что водяные плитки, которые могли бы быть откачаны любым из дренажей, учитываются только один раз.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$h$$$ ($$$1 \leq n \leq 2000, 1 \leq h \leq 10^9$$$) — количество колонок и высота сетки.

Следующая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq h$$$) — высота грязи в колонке $$$i$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное количество водяных плиток, которые можно получить с помощью не более двух дренажей.

Пример
Входные данные
6
7 4
1 3 1 2 3 1 1
8 10
7 5 1 3 2 5 6 8
1 1
1
10 20
5 2 1 2 1 3 6 7 1 1
5 1000000000
1 420420420 1 420420420 1
1 1000000000
1
Выходные данные
14
43
0
170
3738738738
999999999
Примечание

В первом наборе входных данных сетка является примером, показанным в условии. Можно откачать $$$14$$$ плиток воды, установив дренажи, как показано:

Во втором наборе входных данных сетка показана ниже:

Можно откачать все $$$43$$$ плитки воды, установив дренажи, как показано:

В третьем наборе входных данных сетка состоит из одной грязевой плитки, и дренажи установить нельзя. Поэтому ответ равен $$$0$$$.