Билли, Вилли и Московское метро
Мировой экономический кризис 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.
Выходные данные
Выведите одно число — минимальное количество билетов, которые Скрудж должен купить для Билли и Вилли.
Примечание В последнем тесте Скрудж должен дать два билета в первый день, чтобы они перестали действовать на одиннадцатый день, и он должен дать Билли еще один билет.