Агентство
Следуя примеру ряда стартапов по поиску авиабилетов, вы решили создать первый веб-сайт для межпланетных путешествий. Ваша первоочередная задача — быстро определить самый дешевый способ перемещения между двумя планетами. У вас есть преимущество перед конкурентами, так как вы обнаружили, что все планеты и рейсы между ними обладают особой структурой. Каждая планета представлена строкой из N бит, и рейс между двумя планетами возможен, если их N-битные строки отличаются ровно в одной позиции.
Стоимость рейса определяется стоимостью посадки на планету назначения. Если i-й символ в строке планеты равен 1, то необходимо оплатить i-й налог для посадки. Таким образом, стоимость посадки на планету — это сумма всех применимых налогов.
Ваша задача — по заданной начальной планете, конечной планете и стоимости каждого i-го налога вычислить самый дешевый набор рейсов для перемещения от начальной планеты к конечной.
Входные данные
Входные данные для каждого теста состоят из двух строк. Первая строка содержит N (1 ≤ N ≤ 1000), количество бит, представляющих планету; S, строку из N нулей и единиц, представляющую начальную планету; и E, строку, представляющую конечную планету в том же формате. Вторая строка содержит N целых чисел, где i-е число — это стоимость i-го налога. Все стоимости находятся в диапазоне от 1 до 1000000. Ввод завершается строкой, содержащей единственный 0.
Выходные данные
Для каждого теста выведите одно число — минимальную стоимость перемещения от начальной планеты к конечной, используя указанный формат.