{"raw_statement":[{"iden":"statement","content":"The mayor of the Berland city S sees the beauty differently than other city-dwellers. In particular, he does not understand at all, how antique houses can be nice-looking. So the mayor wants to demolish all ancient buildings in the city.\n\nThe city S is going to host the football championship very soon. In order to make the city beautiful, every month the Berland government provides mayor a money tranche. The money has to be spent on ancient buildings renovation.\n\nThere are _n_ months before the championship and the _i_\\-th month tranche equals to _a__i_ burles. The city S has _m_ antique buildings and the renovation cost of the _j_\\-th building is _b__j_ burles.\n\nThe mayor has his own plans for spending the money. As he doesn't like antique buildings he wants to demolish as much of them as possible. For the _j_\\-th building he calculated its demolishing cost _p__j_.\n\nThe mayor decided to act according to the following plan.\n\nEach month he chooses several (possibly zero) of _m_ buildings to demolish in such a way that renovation cost of **each of them separately** is not greater than the money tranche _a__i_ of this month (_b__j_ ≤ _a__i_) — it will allow to deceive city-dwellers that exactly this building will be renovated.\n\nThen the mayor has to demolish all selected buildings during the current month as otherwise the dwellers will realize the deception and the plan will fail. Definitely the total demolishing cost can not exceed amount of money the mayor currently has. The mayor is not obliged to spend all the money on demolishing. If some money is left, the mayor puts it to the bank account and can use it in any subsequent month. Moreover, at any month he may choose not to demolish any buildings at all (in this case all the tranche will remain untouched and will be saved in the bank).\n\nYour task is to calculate the maximal number of buildings the mayor can demolish."},{"iden":"input","content":"The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100 000) — the number of months before the championship and the number of ancient buildings in the city S.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the tranche of the _i_\\-th month.\n\nThe third line contains _m_ integers _b_1, _b_2, ..., _b__m_ (1 ≤ _b__j_ ≤ 109), where _b__j_ is renovation cost of the _j_\\-th building.\n\nThe fourth line contains _m_ integers _p_1, _p_2, ..., _p__m_ (1 ≤ _p__j_ ≤ 109), where _p__j_ is the demolishing cost of the _j_\\-th building."},{"iden":"output","content":"Output single integer — the maximal number of buildings the mayor can demolish."},{"iden":"examples","content":"Input\n\n2 3\n2 4\n6 2 3\n1 3 2\n\nOutput\n\n2\n\nInput\n\n3 5\n5 3 1\n5 2 9 1 10\n4 2 1 3 10\n\nOutput\n\n3\n\nInput\n\n5 6\n6 3 2 4 3\n3 6 4 5 4 2\n1 4 3 2 5 3\n\nOutput\n\n6"},{"iden":"note","content":"In the third example the mayor acts as follows.\n\nIn the first month he obtains 6 burles tranche and demolishes buildings #2 (renovation cost 6, demolishing cost 4) and #4 (renovation cost 5, demolishing cost 2). He spends all the money on it.\n\nAfter getting the second month tranche of 3 burles, the mayor selects only building #1 (renovation cost 3, demolishing cost 1) for demolishing. As a result, he saves 2 burles for the next months.\n\nIn the third month he gets 2 burle tranche, but decides not to demolish any buildings at all. As a result, he has 2 + 2 = 4 burles in the bank.\n\nThis reserve will be spent on the fourth month together with the 4\\-th tranche for demolishing of houses #3 and #5 (renovation cost is 4 for each, demolishing costs are 3 and 5 correspondingly). After this month his budget is empty.\n\nFinally, after getting the last tranche of 3 burles, the mayor demolishes building #6 (renovation cost 2, demolishing cost 3).\n\nAs it can be seen, he demolished all 6 buildings."}],"translated_statement":[{"iden":"statement","content":"伯兰城市S的市长对美的理解与其他市民不同。他完全无法理解为什么古建筑会看起来漂亮。因此，市长希望拆除城市中所有古建筑。\n\n城市S即将举办足球锦标赛。为了使城市变得美丽，政府每月向市长提供一笔资金。这笔钱必须用于古建筑的翻新。\n\n距离锦标赛还有 #cf_span[n] 个月，第 #cf_span[i] 个月的资金为 #cf_span[ai] 卢布。城市S共有 #cf_span[m] 座古建筑，第 #cf_span[j] 座建筑的翻新成本为 #cf_span[bj] 卢布。\n\n市长有自己的资金使用计划。由于他不喜欢古建筑，他希望尽可能多地拆除它们。对于第 #cf_span[j] 座建筑，他计算出了其拆除成本 #cf_span[pj]。\n\n市长决定按照以下计划行事：\n\n每个月，他选择若干（可能为零）座建筑进行拆除，要求每座被选中建筑的翻新成本不超过当月资金 #cf_span[ai]（即 #cf_span[bj ≤ ai]）——这样可以欺骗市民，让他们以为这些建筑将被翻新。\n\n然后，市长必须在当月拆除所有选定的建筑，否则市民会发现欺骗行为，计划将失败。显然，拆除的总成本不能超过市长当前拥有的资金。市长没有义务将所有资金用于拆除。如果有多余资金，市长会将其存入银行账户，并可在之后的任何月份使用。此外，在任何月份，市长都可以选择不拆除任何建筑（此时当月全部资金将被保留并存入银行）。\n\n你的任务是计算市长最多能拆除多少座建筑。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 100 000)] —— 分别表示锦标赛前的月份数和城市S中的古建筑数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 10^9])，其中 #cf_span[ai] 表示第 #cf_span[i] 个月的资金。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[b1, b2, ..., bm] (#cf_span[1 ≤ bj ≤ 10^9])，其中 #cf_span[bj] 表示第 #cf_span[j] 座建筑的翻新成本。\n\n第四行包含 #cf_span[m] 个整数 #cf_span[p1, p2, ..., pm] (#cf_span[1 ≤ pj ≤ 10^9])，其中 #cf_span[pj] 表示第 #cf_span[j] 座建筑的拆除成本。\n\n输出一个整数——市长最多能拆除的建筑数量。\n\n在第三个例子中，市长的行动如下：\n\n第一个月，他获得 #cf_span[6] 卢布资金，并拆除第 #cf_span[#2] 座建筑（翻新成本 #cf_span[6]，拆除成本 #cf_span[4]）和第 #cf_span[#4] 座建筑（翻新成本 #cf_span[5]，拆除成本 #cf_span[2]）。他花光了所有资金。\n\n在获得第二个月 #cf_span[3] 卢布资金后，市长只选择拆除第 #cf_span[#1] 座建筑（翻新成本 #cf_span[3]，拆除成本 #cf_span[1]）。结果，他节省了 #cf_span[2] 卢布用于后续月份。\n\n第三个月，他获得 #cf_span[2] 卢布资金，但决定不拆除任何建筑。结果，他银行中存有 #cf_span[2 + 2 = 4] 卢布。\n\n这笔积蓄将在第四个月与第四个月的资金 #cf_span[4] 一起，用于拆除第 #cf_span[#3] 和 #cf_span[#5] 座建筑（翻新成本均为 #cf_span[4]，拆除成本分别为 #cf_span[3] 和 #cf_span[5]）。该月结束后，他的预算归零。\n\n最后，在获得最后一笔 #cf_span[3] 卢布资金后，市长拆除第 #cf_span[#6] 座建筑（翻新成本 #cf_span[2]，拆除成本 #cf_span[3]）。\n\n可以看出，他总共拆除了全部 #cf_span[6] 座建筑。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 100 000)] —— 分别表示锦标赛前的月份数和城市S中的古建筑数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 10^9])，其中 #cf_span[ai] 表示第 #cf_span[i] 个月的资金。第三行包含 #cf_span[m] 个整数 #cf_span[b1, b2, ..., bm] (#cf_span[1 ≤ bj ≤ 10^9])，其中 #cf_span[bj] 表示第 #cf_span[j] 座建筑的翻新成本。第四行包含 #cf_span[m] 个整数 #cf_span[p1, p2, ..., pm] (#cf_span[1 ≤ pj ≤ 10^9])，其中 #cf_span[pj] 表示第 #cf_span[j] 座建筑的拆除成本。"},{"iden":"output","content":"输出一个整数——市长最多能拆除的建筑数量。"},{"iden":"examples","content":"输入2 32 46 2 31 3 2输出2输入3 55 3 15 2 9 1 104 2 1 3 10输出3输入5 66 3 2 4 33 6 4 5 4 21 4 3 2 5 3输出6"},{"iden":"note","content":"在第三个例子中，市长的行动如下：\n\n第一个月，他获得 #cf_span[6] 卢布资金，并拆除第 #cf_span[#2] 座建筑（翻新成本 #cf_span[6]，拆除成本 #cf_span[4]）和第 #cf_span[#4] 座建筑（翻新成本 #cf_span[5]，拆除成本 #cf_span[2]）。他花光了所有资金。\n\n在获得第二个月 #cf_span[3] 卢布资金后，市长只选择拆除第 #cf_span[#1] 座建筑（翻新成本 #cf_span[3]，拆除成本 #cf_span[1]）。结果，他节省了 #cf_span[2] 卢布用于后续月份。\n\n第三个月，他获得 #cf_span[2] 卢布资金，但决定不拆除任何建筑。结果，他银行中存有 #cf_span[2 + 2 = 4] 卢布。\n\n这笔积蓄将在第四个月与第四个月的资金 #cf_span[4] 一起，用于拆除第 #cf_span[#3] 和 #cf_span[#5] 座建筑（翻新成本均为 #cf_span[4]，拆除成本分别为 #cf_span[3] 和 #cf_span[5]）。该月结束后，他的预算归零。\n\n最后，在获得最后一笔 #cf_span[3] 卢布资金后，市长拆除第 #cf_span[#6] 座建筑（翻新成本 #cf_span[2]，拆除成本 #cf_span[3]）。\n\n可以看出，他总共拆除了全部 #cf_span[6] 座建筑。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of months and antique buildings, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the monthly tranches.  \nLet $ B = (b_1, b_2, \\dots, b_m) \\in \\mathbb{Z}^m $ be the renovation costs of buildings.  \nLet $ P = (p_1, p_2, \\dots, p_m) \\in \\mathbb{Z}^m $ be the demolishing costs of buildings.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 100{,}000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq b_j, p_j \\leq 10^9 $ for all $ j \\in \\{1, \\dots, m\\} $  \n\n**Objective**  \nMaximize the number of buildings demolished, subject to:  \n- In month $ i $, only buildings $ j $ with $ b_j \\leq a_i $ may be selected.  \n- The total demolishing cost of buildings selected in month $ i $ must not exceed the cumulative bank balance at the start of month $ i $ plus $ a_i $.  \n- Unused funds from month $ i $ are carried forward to the bank.  \n- Each building may be demolished at most once.","simple_statement":null,"has_page_source":false}