{"raw_statement":[{"iden":"statement","content":"The kid Andrew doesn't like coins. His country currently uses n different coin types, each with a different value. It is guaranteed that the coin with value 1 is one of the different coin types.\n\nAndrew's weekly taco-pizza grocery list contains r - l + 1 items with costs l, l + 1, ..., r. Unfortunately, Andrew needs to buy each of these items separately as they are sold at different stores. Furthermore, these stores do not give any change, so Andrew must pay the exact amount in coins. Andrew is rather unhappy with the amount of coins he needs to handle every week, so he wants to convince his country to start using a new coin type to minimize the total number of coins needed to buy groceries for his weekly taco-pizza needs. \n\nAndrew is too busy infiltrating UBC, so he wants you to tell him the best coin type to add, or that no new coin types can decrease the amount of coins he needs to use.\n\nThe first line of the input will include an integer n (1 ≤ n ≤ 420), the number of coin types available.\n\nThe next line will include two integers l and r (1 ≤ l ≤ r ≤ 200000, r - l ≤ 50), the range of costs for Andrew's grocery list.\n\nThe next line will include n integers ci (1 ≤ ci ≤ 200000), the value of each coin type that is currently being used. It is guaranteed that no ci is repeated, and there will be some i such that ci = 1.\n\nThe output should contain a single integer. If no new coin type can decrease the total number of coins used, print 0. Otherwise, print a single integer 1 ≤ c ≤ r, the value of the coin type which, when added to the coin system, minimizes the total number of coins Andrew uses. If there are multiple solutions, output any.\n\n"},{"iden":"input","content":"The first line of the input will include an integer n (1 ≤ n ≤ 420), the number of coin types available.The next line will include two integers l and r (1 ≤ l ≤ r ≤ 200000, r - l ≤ 50), the range of costs for Andrew's grocery list.The next line will include n integers ci (1 ≤ ci ≤ 200000), the value of each coin type that is currently being used. It is guaranteed that no ci is repeated, and there will be some i such that ci = 1."},{"iden":"output","content":"The output should contain a single integer. If no new coin type can decrease the total number of coins used, print 0. Otherwise, print a single integer 1 ≤ c ≤ r, the value of the coin type which, when added to the coin system, minimizes the total number of coins Andrew uses. If there are multiple solutions, output any."},{"iden":"examples","content":"Input110 101Output10Input310 151 5 10Output12"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of existing coin types.  \nLet $ [l, r] \\subset \\mathbb{Z} $ be the range of item costs, with $ r - l \\leq 50 $.  \nLet $ C = \\{c_1, c_2, \\dots, c_n\\} \\subset \\mathbb{Z}^+ $ be the set of existing coin values, with $ 1 \\in C $.  \nLet $ S = \\{l, l+1, \\dots, r\\} $ be the set of target amounts to pay exactly.  \n\nFor any coin set $ C' \\supseteq C $, define $ f(C', x) $ as the minimum number of coins from $ C' $ needed to sum to $ x $, using the canonical coin change (unbounded supply).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 420 $  \n2. $ 1 \\leq l \\leq r \\leq 200000 $, $ r - l \\leq 50 $  \n3. $ 1 \\leq c_i \\leq 200000 $, all $ c_i $ distinct, $ 1 \\in C $  \n4. Candidate new coin value $ c $ must satisfy $ 1 \\leq c \\leq r $  \n\n**Objective**  \nCompute:  \n$$\n\\min_{c \\in [1, r] \\setminus C} \\sum_{x = l}^{r} f(C \\cup \\{c\\}, x)\n$$  \nIf the minimum is achieved by no $ c \\in [1, r] \\setminus C $ (i.e., $ \\sum_{x=l}^{r} f(C, x) \\leq \\sum_{x=l}^{r} f(C \\cup \\{c\\}, x) $ for all $ c \\notin C $), output $ 0 $.  \nOtherwise, output any $ c \\in [1, r] \\setminus C $ achieving the minimum.","simple_statement":"Andrew has to buy items costing l, l+1, ..., r (at most 51 different prices). He has n coin types, including 1. He must pay each item’s exact price using coins, and wants to minimize total coins used. He can add ONE new coin (value between 1 and r) to reduce total coins. If no new coin helps, output 0. Otherwise, output any coin value that minimizes the total coins needed.","has_page_source":false}