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