World's economy depression of the 2008 affected everybody in the world and harmed a lot of businesses. But Rich Scrooge McDuck's business suffered most of all. His gold factories started yielding a loss and even went bankrupt. Moreover, the US government revealed that Scrooge was involved in illegal mortgage practices. He had no other option but to leave USA and go abroad. You know what? He chose Russia!
– Uncle Scrooge, we want to try Moscow underground, buy tickets for us! — said Billy and Willy, who had come on their holidays to visit their poor uncle.
– Okey, wait a moment, please — uncle Scrooge answered pensively. He tried to figure out how to spent the least possible money and please his nephews at the same time.
Since Scrooge has never liked mathematics, he needs your help. It is known that Billy and Willy stay in Moscow for n days. They like underground and want to spend some of days to explore it (one trip a day). All the rest days they are going to visit Gorky Park. To prevent squabbles between Billy and Willy, Scrooge needs to give them separate tickets even if they go to underground together. At the end of each day nephews should return their tickets back to uncle. Scrooge has special relations in Moscow underground and can buy tickets for A passages and B days cheaper than they are sold to ordinary people. Certainly, he wants to buy minimum possible number of tickets, so he needs to determine which tickets to give Billy and Willy in the morning. You are hired to help McDuck solve this tricky problem!
Note that the single ticket allows you to use underground no more than A times and the number of days between the first and the last passage should be less than B.
In the first line of the input there is integer n (1 ≤ n ≤ 200) and the integers A and B (1 ≤ A, B ≤ 20). In the second and third lines contain numbers a1, a2, ... , an and b1, b2, ... bn respectively (). Billy uses underground on the ith day if and only if ai = 1. Willy uses underground on the ith day if and only if bi = 1.
Output one number — the minimum number of tickets that Scrooge should buy for Billy and Willy.
In the last test Scrooge should give two tickets at the first day, so they stop working at the eleventh day and he should give Billy one more ticket.
## Input
In the first line of the input there is integer n (1 ≤ n ≤ 200) and the integers A and B (1 ≤ A, B ≤ 20). In the second and third lines contain numbers a1, a2, ... , an and b1, b2, ... bn respectively (). Billy uses underground on the ith day if and only if ai = 1. Willy uses underground on the ith day if and only if bi = 1.
## Output
Output one number — the minimum number of tickets that Scrooge should buy for Billy and Willy.
[samples]
## Note
In the last test Scrooge should give two tickets at the first day, so they stop working at the eleventh day and he should give Billy one more ticket.
**Definitions**
Let $ n \in \mathbb{Z} $, $ A \in \mathbb{Z} $, $ B \in \mathbb{Z} $ be given parameters.
Let $ \mathbf{a} = (a_1, \dots, a_n) \in \{0,1\}^n $, $ \mathbf{b} = (b_1, \dots, b_n) \in \{0,1\}^n $ be binary sequences indicating days Billy and Willy use the underground, respectively.
A ticket is a tuple $ (S, d_1, d_k) $ where:
- $ S \subseteq \{1, \dots, n\} $ is a set of days (at most $ A $ days),
- $ d_1 < d_2 < \dots < d_k $ are the days in $ S $,
- $ d_k - d_1 < B $ (consecutive usage window constraint).
Each ticket covers one person’s underground usage on all days in $ S $.
**Constraints**
1. $ 1 \leq n \leq 200 $
2. $ 1 \leq A, B \leq 20 $
3. For each day $ i \in \{1, \dots, n\} $:
- If $ a_i = 1 $, Billy must be covered by at least one ticket on day $ i $.
- If $ b_i = 1 $, Willy must be covered by at least one ticket on day $ i $.
4. Each ticket covers at most $ A $ days.
5. For any ticket covering days $ d_1 < \dots < d_k $, $ d_k - d_1 < B $.
**Objective**
Minimize the total number of tickets required to cover all days $ i $ where $ a_i = 1 $ (for Billy) and all days $ i $ where $ b_i = 1 $ (for Willy), with separate tickets for each person.