Кирпич — это полоска \(1 \times k\), расположенная горизонтально или вертикально, где \(k\) может быть произвольным числом не менее \(2\) (\(k \ge 2\)).
Кирпичная стена размера \(n \times m\) — это такой способ разместить некоторое количество кирпичей внутри прямоугольника \(n \times m\), чтобы кирпичи располагались по клеткам горизонтально или вертикально, не вылезали за границы прямоугольника \(n \times m\), и чтобы каждая клетка принадлежала ровно одному кирпичу. Здесь \(n\) — это высота прямоугольника \(n \times m\), а \(m\) — ширина. Обратите внимание, что в одной кирпичной стене могут быть кирпичи с разными значениями k.
Устойчивость стены — это число кирпичей, расположенных горизонтально, минус число кирпичей, расположенных вертикально. Обратите внимание, что если вы использовали \(0\) горизонтальных кирпичей и \(2\) вертикальных, то получится устойчивость \(-2\), а не \(2\).
Какую максимальную устойчивость может иметь стена \(n \times m\)?
Гарантируется, что при ограничениях задачи существует хотя бы одна кирпичная стена \(n \times m\).
Примечание
В 1-м тестовом случае максимальная прочность \(2\) получается, если положить два горизонтальных кирпича \(1 \times 2\) друг на друга.
Во 2-м тестовом случае можно получить максимальную прочность \(28\), если разместить в каждом из \(7\) рядов по \(4\) горизонтальных кирпича \(1 \times 2\).