\begin{problem}{Играем в го}{стандартный ввод}{стандартный вывод}{4 секунды}{1024 мегабайта}

Дано $n$ точек на плоскости. Часть из них белые, часть чёрные. Никакие две точки не совпадают. Никакие три точки не лежат на одной прямой.

Вам требуется подвинуть одну из белых точек на расстояние $\leq r$, таким образом, чтобы максимизировать площадь выпуклой оболочки множества точек, которое у вас получится после этой операции.

\InputFile
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $t$ ($1 \le t \le 1\,000$)~--- количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $r$ ($3 \le n \le 2\,000$, $1 \le r \le 10^9$)~--- количество точек и максимальное расстояние для сдвига точки.

Следующие $n$ строк описывают точки. $i$-я из них содержит три целых числа $x_i$, $y_i$ и $c_i$ ($-10^9 \le x_i, y_i \le 10^9$, $1 \le c_i \le 2$)~--- координаты и цвет точки $i$ (1 ~--- белый, 2 ~--- черный).

Гарантируется, что сумма $n$ по всем наборам входных данных в каждом тесте не превосходит $2\,000$.

\OutputFile
Для каждого набора входных данных в отдельной строке выведите одно число~--- максимальную площадь выпуклой оболочки этого множества точек, если любую из белых можно сдвинуть не больше чем на $r$.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $10^{-6}$.

Формально, пусть ваш ответ равен $a$, а ответ жюри равен $b$. Ваш ответ будет зачтен, если и только если $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\end{example}

\Note
Ниже приведены картинки для примеров из условия. Пунктирной линией обозначены ребра новой выпуклой оболочки, сплошной~--- ребра старой выпуклой оболочки и общие ребра. Синей стрелкой показано оптимальное движение белой точки.

\begin{center}
\includegraphics[scale=0.9]{drawH.1}

\small{Пример 1}
\end{center}

\begin{center}
\includegraphics[scale=0.6]{drawH.2}

\small{Пример 2}
\end{center}

\begin{center}
\includegraphics[scale=0.6]{drawH.3}

\small{Пример 3}
\end{center}

\Scoring
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия может не требоваться для некоторых групп. \textbf{Offline-проверка} означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.

Обозначим за $\sum n$ ~--- сумму $n$ по всем наборам входных данных данного теста.

\medskip
\begin{center}
\begingroup
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& & \multicolumn{1}{c|}{Доп. ограничения} & & \\
\cline{3-3}
\raisebox{2.25ex}[0cm][0cm]{Группа}
& \raisebox{2.25ex}[0cm][0cm]{Баллы}
& $\sum n$
& \raisebox{2.25ex}[0cm][0cm]{\parbox{1.5cm}{\centering Необх. группы}}
& \raisebox{2.25ex}[0cm][0cm]{Комментарий}
\\
\hline
0       & 0     & --                & --       & Тесты из условия             \\
\hline
1       & 11     & $\sum n \le 3$    & 0        &                               \\
\hline
2       & 18    & $\sum n \le 30$   & 0, 1 &                               \\
\hline
3       & 6    & $\sum n \le 50$   & 0, 1, 2 &                               \\
\hline
4       & 13     & $\sum n \le 200$  & --       & Все точки на выпуклой оболочке черные \\
\hline
5       & 14    & $\sum n \le 200$  & 0 -- 4 &                               \\
\hline
6       & 8     & $\sum n \le 500$  & 4        & Все точки на выпуклой оболочке черные \\
\hline
7       & 7    & $\sum n \le 500$  & 0 -- 6 &                               \\
\hline
8       & 12    & $\sum n \le 2000$ & 4, 6     & \parbox{8cm}{\centering \vspace{2mm} {Все точки на выпуклой оболочке черные. \\ \textbf{Offline-проверка}}\vspace{2mm}}  \\
\hline
9       & 11   & $\sum n \le 2000$ & 0 -- 8 & \textbf{Offline-проверка}    \\
\hline
\end{tabular}
\endgroup
\end{center}

\end{problem}

