{"raw_statement":[{"iden":"statement","content":"World’s economy depression of the 2008 affected everybody in the world and harmed a lot of businesses.\n\nBut 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!\n\n– 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.\n\n– 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.\n\nSince 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!\n\nNote 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.\n\nIn 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 a1, a2, ..., an and b1, b2, ..., bn, respectively (). Billy uses the underground on the i-th day if and only if ai = 1. Willy uses the underground on the i-th day if and only if bi = 1.\n\nOutput one number — the minimum number of tickets that Scrooge should buy for Billy and Willy.\n\n"},{"iden":"input","content":"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 a1, a2, ..., an and b1, b2, ..., bn, respectively (). Billy uses the underground on the i-th day if and only if ai = 1. Willy uses the underground on the i-th day if and only if bi = 1."},{"iden":"output","content":"Output one number — the minimum number of tickets that Scrooge should buy for Billy and Willy."},{"iden":"examples","content":"Input2 5 51 10 0Output1Input2 5 51 00 1Output1Input11 20 101 1 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 0 0Output3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ A, B \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ \\mathbf{a} = (a_1, \\dots, a_n), \\mathbf{b} = (b_1, \\dots, b_n) \\in \\{0,1\\}^n $ be binary sequences indicating days Billy and Willy use the underground, respectively.  \nLet $ D_b = \\{ i \\in \\{1,\\dots,n\\} \\mid a_i = 1 \\} $, $ D_w = \\{ i \\in \\{1,\\dots,n\\} \\mid b_i = 1 \\} $ be the sets of days Billy and Willy use the underground.\n\nA ticket allows at most $ A $ uses and must cover a contiguous interval of days of length less than $ B $ (i.e., if used on days $ d_1 < d_2 < \\dots < d_k $, then $ d_k - d_1 < B $).\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200 $  \n2. $ 1 \\leq A, B \\leq 20 $  \n3. Each ticket can cover at most $ A $ uses and must span fewer than $ B $ days between first and last use.\n\n**Objective**  \nFind the minimum total number of tickets required to cover all uses by Billy and Willy, where each use (day) must be covered by exactly one ticket per person, and tickets cannot be shared between Billy and Willy.","simple_statement":"Scrooge needs to buy subway tickets for Billy and Willy for n days.  \nEach day, if ai=1, Billy takes the subway; if bi=1, Willy takes it.  \nEach ticket allows up to A rides and must be used within B consecutive days.  \nThey must each have their own ticket.  \nFind the minimum number of tickets needed for both.","has_page_source":false}