Для Мірка немає більшого щастя, ніж знайти новий рулон скотчу, а сьогодні він особливо щасливий, тому що знайшов адвент-календар Славка.

Адвент-календар можна представити як таблицю з ~n~ рядків та ~m~ стовпців. Кожна клітинка містить маленьке віконце, а за кожним віконцем знаходиться шматочок шоколаду. Славко вже відкрив деякі віконця, а інші все ще закриті.

Мірко вирішив використати свій скотч, щоб заклеїти всі закриті віконця. Скотч нескінченно довгий і шириною в одну клітинку календаря. Мірко може відірвати шматок скотчу і використати його, щоб заклеїти певну послідовність закритих віконець, що прилягають горизонтально або вертикально. Він не хоче наклеювати більше одного шматка скотчу на одне віконце, оскільки хоче залишитися другом Славка.

Він хоче дізнатися, яка мінімальна кількість шматків скотчу потрібна, щоб заклеїти всі закриті віконця.

Input

Перший рядок містить цілі числа ~n~ та ~m~ ~(1 \leq n \leq 1000, 1 \leq m \leq 10)~ - розміри адвент-календаря.

Кожен з наступних ~n~ рядків містить ~m~ символів "." та #, що представляють адвент-календар. Символ "." позначає відкрите віконце, а символ # позначає закрите віконце.

Output

Виведіть мінімальну кількість шматків скотчу, необхідну для заклеювання всіх закритих віконець.

Оцінювання

1. (~25~ балів): Кожне закрите віконце прилягає (має спільну сторону) максимум до двох інших закритих віконець;

2. (~35~ балів): ~n \leq 10~;

3. (~40~ балів): без додаткових обмежень.