{"raw_statement":[{"iden":"background","content":"Lana 和 Fran 正在参观一家巧克力工厂，现在他们想买些巧克力。"},{"iden":"statement","content":"巧克力工厂里有 $n$ 块不同的巧克力，其中第 $i$ 块的价格为 $c_i$。Lana 和 Fran 想买 $m$ 块巧克力。\n\nFran 有一个消费方案：\n\n•如果巧克力价格低于 $k$ 元，这块巧克力的费用将全部由 Lana 支付。\n\n•否则，Lana 将支付 $k$ 元，而 Fran 将支付其余的部分，即 $c_i−k$ 元。\n\nLana 对 Fran 的方案不满意，想要报复 Fran。设 $l$ 为 Lana 需要支付的金额，$f$ 为 Fran 需要支付的金额。Lana 将选择使 $l−f$ 的值最小的购买方案。\n\n由于 Fran 还在犹豫，不知道要买多少巧克力，所以 Lana 想知道对于给出的 $q$ 种不同的购买方案 $k_i$ 和 $m_i$，每种方案 $l−f$ 的最小值。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$，分别表示巧克力的数量和询问数量。\n\n第二行包含 $n$ 个整数 $c_i$，依次表示每块巧克力的价格。\n\n接下来 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$，分别表示 Fran 的付款阈值和购买的巧克力总数量。"},{"iden":"output","content":"输出 $q$ 行，每行一个整数表示 Lana 询问的答案。"},{"iden":"note","content":"| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $n,q \\leq 1000,c_i,k_i\\leq 10^6$ |\n| $2$ | $20$ | 所有询问的 $k$ 都相等 |\n| $3$ | $35$ | 无特殊性质 |\n\n对于 $100\\%$ 的数据，$1\\leq m_i\\leq n,q\\leq 10^5,1\\leq c_i,k_i \\leq 10^9$。\n\n本题满分 $70$ 分。"}],"translated_statement":null,"sample_group":[["5 2\n1 9 22 10 19\n18 4\n5 2","34\n-21"],["7 4\n1 5 4 3 7 11 9\n5 4\n5 7\n7 3\n4 5","4\n16\n7\n1"],["3 3\n5 6 7\n10 1\n5 3\n3 3","5\n12\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}