Наигравшись на бумаге, Яхуб перешел на компьютерные игры. Он играет в игру под названием «Башни из кирпичей». Играется она на прямоугольной таблице, состоящей из n строк и m столбцов (таблица содержит n × m ячеек). Цель игры — построить свой собственный город. Некоторые ячейки таблицы — это огромные дыры, и там Яхуб никакого здания построить не может. Остальные ячейки — пустые. В некоторой пустой ячейке можно построить ровно одну башню одного из двух следующих видов:

1. Синие башни. Лимит населения каждой равен 100.
2. Красные башни. Лимит населения каждой равен 200. Однако, красную башню можно построить в некоторой ячейке только тогда, когда на момент постройки хотя бы одна из соседних ячеек имеет синюю башню. Две ячейки являются соседними, если они имеют общую сторону.

Яхубу также разрешено уничтожить здание в любой ячейке. Он может выполнять эту операцию какое угодно количество раз. Уничтожение одного здания не влияет на остальные здания, а ячейка, в которой уничтожили здание, становится пустой (таким образом, Яхуб может, если это нужно, построить башню в этой ячейке — такой случай показан во втором примере).

Яхуб может привезти в свой город столько населения, сколько хочет. Итак, ему нужно построить свой город так, чтобы в нем помещалось как можно больше людей. То есть нужно найти оптимальную последовательность застройки, такую, что итоговый суммарный лимит населения как можно больше.

Яхуб говорит, что в этой игре он лучший, и все же, у него нет оптимального решения. Напишите программу, которая высчитывает оптимальное решение и покажите зазнайке, что он не так уж и крут!