{"problem":{"name":"[语言月赛 202210] 垃圾分类","description":{"content":"2077 年，由于资源几近枯竭，梦之城推行了一套极其严格的垃圾分类制度。具体的，梦之城将垃圾分为 $n$ 类，每一类垃圾只能被放入特定的垃圾桶中。由于梦之城掌握了压缩技术，因此在这里**垃圾只有数量之分，没有体积大小之分。** 你是梦之城的一位居民。在你居住的社区外有 $n + 1$ 个垃圾桶，标号为 $1, 2, \\cdots, n, n + 1$。 对前 $n$ 个垃圾桶，它们只能接受**","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P1"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3673"},"statements":[{"statement_type":"Markdown","content":"2077 年，由于资源几近枯竭，梦之城推行了一套极其严格的垃圾分类制度。具体的，梦之城将垃圾分为 $n$ 类，每一类垃圾只能被放入特定的垃圾桶中。由于梦之城掌握了压缩技术，因此在这里**垃圾只有数量之分，没有体积大小之分。**\n\n你是梦之城的一位居民。在你居住的社区外有 $n + 1$ 个垃圾桶，标号为 $1, 2, \\cdots, n, n + 1$。\n\n对前 $n$ 个垃圾桶，它们只能接受**对应标号**的垃圾，并且有一定的容量。具体的，你会得到一个长度为 $n$ 的序列 $r _ 1, \\cdots, r _ n$。第 $i$ 个垃圾桶只能接受第 $i$ 类垃圾，且最多只能被放入 $r _ i$ 个。\n\n对最后一个垃圾桶，它可以接受所有种类的垃圾，容量也是几近无限的。但是，每向**这个**垃圾桶放入一个垃圾，居委会会向你收取 $c$ 的费用。\n\n某一天，你的家中堆放满了垃圾。在将这些垃圾分类好后，你得到了一个长度为 $n$ 的序列 $a _ 1, \\cdots, a _ n$，代表第 $i$ 类垃圾有 $a _ i$ 个。\n\n你想要知道，如果想要扔掉所有的这些垃圾，你的最小花费是多少。\n\n## Input\n\n共三行。\n\n第一行两个整数 $n, c$，代表垃圾的种类数和向最后一个垃圾桶放入垃圾的费用。\n\n第二行 $n$ 个整数 $r _ 1, \\cdots, r _ n$，代表垃圾桶的容量。\n\n第三行 $n$ 个整数 $a _ 1, \\cdots, a _ n$，代表每一类垃圾的数量。\n\n## Output\n\n一行一个整数，代表最小花费。\n\n[samples]\n\n## Note\n\n**样例解释**\n\n样例组 #1：最优情况下，你需要向最后一个垃圾桶中放入 $9$ 个垃圾，费用为 $7 \\times 9 = 63$。\n\n样例组 #2：最优情况下，你不需要向最后一个垃圾桶中放入任何垃圾，费用为 $0$。\n\n**数据规模与约定**\n\n对前 $20\\%$ 的数据，保证 $n = 2$。\n\n对前 $60\\%$ 的数据，保证 $n, a _ i, c \\leq 10 ^ 3$。\n\n对另外 $10\\%$ 的数据，保证 $c = 0$。\n\n对另外 $10\\%$ 的数据，保证 $r _ i \\geq a _ i$。\n\n对 $100\\%$ 的数据，保证 $2 \\leq n \\leq 10 ^ 6, 0 \\leq r _ i, a _ i, c \\leq 10 ^ 6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3673","tags":["2022","O2优化","数组","语言月赛"],"sample_group":[["2 7\n4 3\n7 9","63"],["2 10000\n100 100\n3 7","0"]],"created_at":"2026-03-03 11:09:25"}}