CF1106B Lunar New Year and Food Ordering

春节临近，Bob 计划去一家著名餐厅——“Alice's”。 餐厅 “Alice's” 提供 $n$ 种不同的菜品。第 $i$ 种菜品的价格始终为 $c_i$。最初，餐厅恰好有 $a_i$ 份第 $i$ 种菜品的原料。在除夕夜，将有 $m$ 位顾客依次光临 Alice's，第 $j$ 位顾客将点 $d_j$ 份第 $t_j$ 种菜品。第 $i+1$ 位顾客只有在第 $i$ 位顾客完全被服务后才会到来。 假设当前第 $i$ 种菜品还剩 $r_i$ 份（初始时 $r_i = a_i$）。当顾客点 $1$ 份第 $i$ 种菜品时，将按照以下规则处理： 1. 如果 $r_i > 0$，则顾客将被准确地供应 $1$ 份第 $i$ 种菜品，费用为 $c_i$，同时 $r_i$ 减 $1$。 2. 否则，如果 $i$ 种菜品已售罄，则顾客将被供应当前仍有剩余的菜品中价格最低的一种（如有多种价格最低，则选择编号最小的那种）。费用为所供应菜品的价格，相应菜品的剩余量减 $1$。 3. 如果所有菜品都已售罄，则顾客愤然离开。无论之前已供应多少份菜品，该顾客的消费金额均为 $0$。 如果顾客在被供应完 $d_j$ 份菜品后没有离开，则该顾客的消费金额为这 $d_j$ 份菜品的总费用。 请你计算每一位顾客的总消费金额。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示菜品种类数和顾客人数。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^7$），其中 $a_i$ 表示第 $i$ 种菜品的初始剩余量。 第三行包含 $n$ 个正整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^6$），其中 $c_i$ 表示第 $i$ 种菜品的单价。 接下来 $m$ 行，每行描述一位顾客的点单。第 $j$ 行包含两个正整数 $t_j$ 和 $d_j$（$1 \leq t_j \leq n$，$1 \leq d_j \leq 10^7$），分别表示点单的菜品种类和数量。

输出 $m$ 行，第 $j$ 行输出第 $j$ 位顾客的消费金额。

在第一个样例中，5 位顾客的服务情况如下： 1. 顾客 1 被供应了 6 份第 2 种菜品、1 份第 4 种菜品和 1 份第 6 种菜品。消费金额为 $6 \times 3 + 1 \times 2 + 1 \times 2 = 22$。8 种菜品的剩余量变为 $\{8, 0, 2, 0, 4, 4, 7, 5\}$。 2. 顾客 2 被供应了 4 份第 1 种菜品。消费金额为 $4 \times 6 = 24$。剩余量变为 $\{4, 0, 2, 0, 4, 4, 7, 5\}$。 3. 顾客 3 被供应了 4 份第 6 种菜品、3 份第 8 种菜品。消费金额为 $4 \times 2 + 3 \times 2 = 14$。剩余量变为 $\{4, 0, 2, 0, 4, 0, 7, 2\}$。 4. 顾客 4 被供应了 2 份第 3 种菜品、2 份第 8 种菜品。消费金额为 $2 \times 3 + 2 \times 2 = 10$。剩余量变为 $\{4, 0, 0, 0, 4, 0, 7, 0\}$。 5. 顾客 5 被供应了 7 份第 7 种菜品、3 份第 1 种菜品。消费金额为 $7 \times 3 + 3 \times 6 = 39$。剩余量变为 $\{1, 0, 0, 0, 4, 0, 0, 0\}$。 在第二个样例中，除了最后一位顾客外，其余顾客都能被完全供应。例如，第二位顾客被供应了 6 份第 2 种菜品，消费金额为 $66 \times 6 = 396$。 在第三个样例中，有些顾客未能完全按所点菜品被供应。例如，第二位顾客被供应了 6 份第 2 种菜品、6 份第 3 种菜品和 1 份第 4 种菜品，消费金额为 $66 \times 6 + 666 \times 6 + 6666 \times 1 = 11058$。 由 ChatGPT 4.1 翻译