Саша увлекается программированием компьютерных игр. Вот уже три для он пишет новую игру для сотового телефона под названием "Битва титанов". Героями игрушки являются оловянные солдатики. В качестве прототипа для описания действий оловянного солдатика Саша взял шахматную ладью.

Шахматная ладья - это фигура, которая может перемещаться на любое количество клеток по вертикали или горизонтали. Ладьи не могут перемещаться за препятствия. Задача - вычислить максимальное количество ладей, которые можно поставить на доске так, чтобы никакие две не били друг друга. Это означает, что конфигурация правильна при условии, что никакие две ладьи не находятся на одной горизонтали или вертикали в пределах видимости друг друга.

Следующий пример показывает пять изображений. Первое изображение является пустым, второе и третье изображения показывают правильные конфигурации, а четвертый и пятый рисунок - примеры неправильных конфигураций.

Помогите Саше поскорее закончить программу и вычислите максимальное количество ладей на заданной конфигурации доски.

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.

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

Задана последовательность цифр. Определите, можно ли расставить между некоторыми из них знаки "+" и "-", так чтобы получилось заданное число \(M\), но никакие промежуточные вычисления не превосходили по модулю \(10000\).