Задача J. Join The Team

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

Команда финалистов ICPC состоит из x олимпиадных программистов и y тренеров. Так как еще одна из проблем космических электричек - непрочная обшивка (чтобы максимально увеличить грузоподъёмность летательного аппарата), крайне не рекомендуется вести громких разговоров в вагоне. А наши финалисты очень любят пошуметь и поиграть в различные игры... Да и тренеры не прочь обсудить друг с другом методы обучения и новые типы задач. Поэтому компания-перевозчик обязала рассадить финалистов определенным способом для их же безопасности.

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

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

Формат входных данных

В первой строке следует три целых числа n, x и y (1 ≤ n ≤ 106, 0 ≤ x,y ≤ 106, x + y ≠ 0) — общее количество мест в вагоне, количество участников и тренеров.

Во второй строке следует строка длины n, состоящая из символов . и #. Точка означает, что соответствующее место свободно. Звездочка означает, что соответствующее место занято межпланетным путешественником.

Формат выходных данных

Выведите наибольшее количество людей, которых можно посадить вышеописанным способом.

Ограничения

1 ≤ n ≤ 106

0 ≤ x,y ≤ 106

x + y > 0

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
na,b
1101 ≤ n ≤ 100 ≤ a,b ≤ 10
2351 ≤ n ≤ 1030 ≤ a,b ≤ 103
3551 ≤ n ≤ 1060 ≤ a,b ≤ 106

Пояснение к примерам

Далее воспринимаем X как участника и Y как тренера.

В примере можно посадить всех людей, например, следующим образом:

XY#YX

Примеры тестов

Стандартный вход Стандартный выход
1
5 3 2
..#..
4

0.081s 0.008s 13