Министерство инноваций утвердило приказ о построении ВСПД, объединяющей две столицы. Все, конечно, поняли, что речь о высокоскоростной пешеходной дороге, но никто не знал, как её строить. К счастью, в городе нашелся единственный в мире завод по производству комплектующих для СПД.

Завод производит m типов плиток в форме прямоугольников размеров 1 × k см, доступных в c_k различных цветах, 1 ≤ k ≤ m.

Дорога состоит из прямоугольных сегментов размера 2 × n см. Каждый сегмент при строительстве собирается из плиток указанного вида. Поскольку готовую дорогу будет принимать высокое начальство, решено её строить из уникальных сегментов, то есть все сегменты должны отличаться способом покрытия плиткой.

Теперь важно выяснить, каково максимальное возможное количество уникальных сегментов.