400551: GYM100203 J Journeys on the Moscow Underground

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.

– Okay, wait a moment, please — uncle Scrooge answered pensively. He tried to figure out how to spend 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 an integer n (1 ≤ n ≤ 200) and integers A and B (1 ≤ A, B ≤ 20). The second and third lines contain numbers a₁, a₂, ..., a_n and b₁, b₂, ..., b_n, respectively (). Billy uses the underground on the i-th day if and only if a_i = 1. Willy uses the underground on the i-th day if and only if b_i = 1.

Output one number — the minimum number of tickets that Scrooge should buy for Billy and Willy.

2 5 5
1 1
0 0

1

2 5 5
1 0
0 1

1

11 20 10
1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0

3