{"raw_statement":[{"iden":"statement","content":"The marmots need to prepare _k_ problems for HC2 over _n_ days. Each problem, once prepared, also has to be printed.\n\nThe preparation of a problem on day _i_ (at most one per day) costs _a__i_ CHF, and the printing of a problem on day _i_ (also at most one per day) costs _b__i_ CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine).\n\nWhat is the minimum cost of preparation and printing?"},{"iden":"input","content":"The first line of input contains two space-separated integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 2200). The second line contains _n_ space-separated integers _a_1, ..., _a__n_ () — the preparation costs. The third line contains _n_ space-separated integers _b_1, ..., _b__n_ () — the printing costs."},{"iden":"output","content":"Output the minimum cost of preparation and printing _k_ problems — that is, the minimum possible sum _a__i_1 + _a__i_2 + ... + _a__i__k_ + _b__j_1 + _b__j_2 + ... + _b__j__k_, where 1 ≤ _i_1 < _i_2 < ... < _i__k_ ≤ _n_, 1 ≤ _j_1 < _j_2 < ... < _j__k_ ≤ _n_ and _i_1 ≤ _j_1, _i_2 ≤ _j_2, ..., _i__k_ ≤ _j__k_."},{"iden":"example","content":"Input\n\n8 4\n3 8 7 9 9 4 6 8\n2 5 9 4 3 8 9 1\n\nOutput\n\n32"},{"iden":"note","content":"In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"旱獭需要在 #cf_span[n] 天内为 HC#cf_span[2] 准备 #cf_span[k] 道题目，每道题目准备完成后必须打印。\\n\\n在第 #cf_span[i] 天准备一道题目（每天最多准备一道）的费用为 #cf_span[ai] CHF，在第 #cf_span[i] 天打印一道题目（每天最多打印一道）的费用为 #cf_span[bi] CHF。当然，一道题目不能在被准备之前被打印（但在同一天完成准备和打印是允许的）。\\n\\n准备和打印的最小总费用是多少？\\n\\n输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（）——准备费用。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn]（）——打印费用。\\n\\n请输出准备和打印 #cf_span[k] 道题目的最小费用——即最小可能的和 #cf_span[ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk]，其中 #cf_span[1 ≤ i1 < i2 < ... < ik ≤ n]，#cf_span[1 ≤ j1 < j2 < ... < jk ≤ n]，且满足 #cf_span[i1 ≤ j1]，#cf_span[i2 ≤ j2]，...，#cf_span[ik ≤ jk]。\\n\\n在样例测试用例中，一种最优解是：在第 #cf_span[1] 天准备第一道题并在第 #cf_span[1] 天打印，第 #cf_span[2] 天准备第二道题并在第 #cf_span[4] 天打印，第 #cf_span[3] 天准备第三道题并在第 #cf_span[5] 天打印，第 #cf_span[6] 天准备第四道题并在第 #cf_span[8] 天打印。\"}},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（）——准备费用。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn]（）——打印费用。\"},{\"iden\":\"output\",\"content\":\"请输出准备和打印 #cf_span[k] 道题目的最小费用——即最小可能的和 #cf_span[ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk]，其中 #cf_span[1 ≤ i1 < i2 < ... < ik ≤ n]，#cf_span[1 ≤ j1 < j2 < ... < jk ≤ n]，且满足 #cf_span[i1 ≤ j1]，#cf_span[i2 ≤ j2]，...，#cf_span[ik ≤ jk]。\"},{\"iden\":\"note\",\"content\":\"在样例测试用例中，一种最优解是：在第 #cf_span[1] 天准备第一道题并在第 #cf_span[1] 天打印，第 #cf_span[2] 天准备第二道题并在第 #cf_span[4] 天打印，第 #cf_span[3] 天准备第三道题并在第 #cf_span[5] 天打印，第 #cf_span[6] 天准备第四道题并在第 #cf_span[8] 天打印。\"}]","sample_group":[],"show_order":[],"formal_statement":"Let $ n, k \\in \\mathbb{N} $ with $ 1 \\leq k \\leq n \\leq 2200 $.  \nGiven two sequences $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{R}^n $ and $ b = (b_1, b_2, \\dots, b_n) \\in \\mathbb{R}^n $, representing preparation and printing costs per day, respectively.\n\nWe seek to choose two strictly increasing sequences of indices:\n- $ i_1 < i_2 < \\dots < i_k $ (days of preparation),\n- $ j_1 < j_2 < \\dots < j_k $ (days of printing),\n\nsuch that $ i_\\ell \\leq j_\\ell $ for all $ \\ell = 1, 2, \\dots, k $,  \nand minimize the total cost:\n$$\n\\sum_{\\ell=1}^k a_{i_\\ell} + \\sum_{\\ell=1}^k b_{j_\\ell}.\n$$\n\n**Objective:**  \nMinimize $ \\sum_{\\ell=1}^k (a_{i_\\ell} + b_{j_\\ell}) $  \nsubject to $ 1 \\leq i_1 < i_2 < \\dots < i_k \\leq n $,  \n$ 1 \\leq j_1 < j_2 < \\dots < j_k \\leq n $,  \nand $ i_\\ell \\leq j_\\ell $ for all $ \\ell \\in \\{1, \\dots, k\\} $.","simple_statement":null,"has_page_source":false}