Біллі, Віллі та Московське метро
Світова економічна депресія 2008 року вплинула на всіх у світі та завдала шкоди багатьом бізнесам. Але бізнес багатого Скруджа МакДака постраждав найбільше. Його золоті фабрики почали приносити збитки і навіть збанкрутували. Більше того, уряд США виявив, що Скрудж був залучений до незаконних іпотечних практик. У нього не було іншого вибору, окрім як покинути США і поїхати за кордон. Знаєте що? Він обрав Росію!
– Дядьку Скрудж, ми хочемо спробувати московське метро, купи нам квитки! — сказали Біллі та Віллі, які приїхали на канікули відвідати свого бідного дядька.
– Добре, зачекайте хвилинку, будь ласка — відповів дядько Скрудж задумливо. Він намагався зрозуміти, як витратити якомога менше грошей і водночас порадувати своїх племінників.
Оскільки Скрудж ніколи не любив математику, йому потрібна ваша допомога. Відомо, що Біллі та Віллі залишаються в Москві n днів. Вони люблять метро і хочуть провести кілька днів, досліджуючи його (одна поїздка на день). Усі інші дні вони збираються відвідати парк Горького. Щоб уникнути сварок між Біллі та Віллі, Скрудж повинен дати їм окремі квитки, навіть якщо вони їдуть у метро разом. Наприкінці кожного дня племінники повинні повернути свої квитки дядькові. Скрудж має особливі відносини в московському метро і може купувати квитки на A поїздок і B днів дешевше, ніж вони продаються звичайним людям. Звичайно, він хоче купити мінімально можливу кількість квитків, тому йому потрібно визначити, які квитки дати Біллі та Віллі вранці. Вас найняли, щоб допомогти МакДаку вирішити цю складну задачу!
Зверніть увагу, що один квиток дозволяє використовувати метро не більше ніж A разів, а кількість днів між першою та останньою поїздкою має бути меншою за B.
Вхідні дані
У першому рядку введення знаходиться ціле число n (1 ≤ n ≤ 200) та цілі числа A і B (1 ≤ A, B ≤ 20). У другому та третьому рядках містяться числа a_1, a_2, ..., a_n та b_1, b_2, ..., b_n відповідно (a_i, b_i ∈ {0, 1}). Біллі користується метро в i-ий день, якщо і тільки якщо a_i = 1. Віллі користується метро в i-ий день, якщо і тільки якщо b_i = 1.
Вихідні дані
Виведіть одне число — мінімальну кількість квитків, які Скрудж повинен купити для Біллі та Віллі.
Примітка У останньому тесті Скрудж повинен дати два квитки в перший день, щоб вони перестали діяти на одинадцятий день, і він повинен дати Біллі ще один квиток.