Омкар строит дом. Он хочет решить, как составить план пола на последнем этаже.
Пол Омкара изначально выглядит как \(n\) строк по \(m\) нолей. (\(1 \le n,m \le 100\)). Каждая строка разделена на отрезки, причем каждый \(0\) в строке находится ровно в \(1\) отрезке. Для каждого отрезка для каждой строки Омкар может заменить ровно один из \(0\), содержащихся в этом отрезке, на \(1\). Омкар определяет качество пола как сумму квадратов сумм значений в каждом столбце, т.е. если сумма значений в \(i\)-м столбце равна \(q_i\), то качество пола равно \(\sum_{i = 1}^m q_i^2\).
Помогите Омкару найти максимальное качество, которое может иметь пол.
Выходные данные
Выведите одно целое число, которое является максимально возможным качеством пола.
Примечание
Данный пример соответствует следующей диаграмме. Ячейки в одном ряду с одинаковым номером являются частью одного и того же отрезка.
Наиболее оптимальным планом является:
Сумма \(1\)-го столбца равна \(4\), сумма \(2\)-го столбца равна \(2\), сумма \(3\)-го и \(4\)-го столбцов равна \(0\), а сумма \(5\)-го столбца равна \(4\).
Качество этого плана этажа составляет \(4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36\). Можно показать, что нет плана пола с более высоким качеством.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 2 1 2 3 5 2 1 3 4 5 3 1 1 2 4 5 5 3 1 1 2 2 3 5
|
36
|