Стековий лабіринт
Є лабіринт, який можна описати як сітку розміром W×H. Верхня ліва клітинка позначається як (1, 1), а нижня права клітинка — (W, H). Ви починаєте в клітинці (1, 1) і повинні дістатися до клітинки (W, H). Ви можете рухатися лише до сусідньої клітинки праворуч або вниз. Нижче наведено приклад лабіринту.
У лабіринті деякі клітинки вільні (позначені '.'), а деякі зайняті камінням (позначені '#'), куди ви не можете зайти. У деяких вільних клітинках є коштовності (позначені малими літерами), а також отвори для розміщення коштовностей (позначені великими літерами). Різні літери відповідають різним типам коштовностей: клітинка, позначена 'a', містить коштовність типу A, а клітинка, позначена 'A', містить отвір для розміщення коштовності типу A. Коли ви розміщуєте коштовність у відповідний отвір, відбувається щось приємне.
У клітинках з коштовностями ви можете вибрати, чи брати коштовність чи ні. Аналогічно, у клітинках з отворами ви можете вибрати, чи розміщувати коштовність, яку маєте, чи ні. Спочатку у вас немає жодних коштовностей. У вас є дуже велика сумка, тому ви можете нести скільки завгодно коштовностей. Однак ваша сумка — це стек, тобто ви можете розмістити лише ту коштовність, яку взяли останньою.
На шляху від клітинки (1, 1) до клітинки (W, H), скільки коштовностей ви можете розмістити у відповідні отвори?
Вхідні дані
Вхід містить послідовність наборів даних. Кінець введення позначається рядком, що містить два нулі. Кожен набір даних відформатовано наступним чином.
H W
C_11 C_12 ... C_1W
C_21 C_22 ... C_2W
...
C_H1 C_H2 ... C_HW
Тут H і W — це висота і ширина сітки. Ви можете припустити, що 1 ≤ W, H ≤ 50. Решта наборів даних складається з H рядків, кожен з яких складається з W літер. Кожна літера C_ij визначає тип клітинки (i, j), як описано раніше. Гарантується, що C_11 і C_WH ніколи не є '#'.
Ви також можете припустити, що кожна мала або велика літера з'являється не більше 10 разів у кожному наборі даних.
Вихідні дані
Для кожного набору даних виведіть максимальну кількість коштовностей, які ви можете розмістити у відповідні отвори. Якщо ви не можете дістатися до клітинки (W, H), виведіть -1.