На бесконечном клетчатом листе бумаги выбираются \(n\) клеток и окрашиваются в три цвета, где \(n\) кратно \(3\). Оказывается, что есть ровно \(\frac{n}{3}\) отмеченных клеток каждого из трех цветов!
Найдите наибольшее такое \(k\), при котором можно выбрать \(\frac{k}{3}\) клеток каждого цвета, удалить все остальные помеченные клетки, а затем выбрать три прямоугольника со сторонами, параллельными линиям сетки, так, чтобы выполнялись следующие условия:
- Никакие два прямоугольника не могут пересекаться (но они могут иметь общую часть границы). Другими словами, площадь пересечения любых двух прямоугольников должна быть равна \(0\).
- \(i\)-й прямоугольник содержит все выбранные клетки \(i\)-го цвета и ни одной выбранной клетки другого цвета, для \(i = 1, 2, 3\).
Выходные данные
Выведите одно целое число \(k\) — наибольшее количество клеток, которое можно оставить.
Примечание
В первом примере можно оставить \(6\) клеток с индексами \(1, 5, 6, 7, 8, 9\).
Во втором примере можно оставить \(3\) клетки с индексами \(1, 2, 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
2 3 1
4 1 2
2 1 3
3 4 1
5 3 2
4 4 3
2 4 1
5 2 2
3 5 3
|
6
|
|
2
|
3
1 1 1
2 2 2
3 3 3
|
3
|