当前没有测试数据。

NZIC 2026 Round 1

Alchemy（炼金术）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 256 MB 时间限制： 2.5 秒

原题来源：

NZIC 2026 Round 1（新西兰信息学竞赛 2026 第一轮）

---

题目描述

技艺高超的炼金术士 Zalán 每天都在自己的实验室里辛勤工作，把不同种类的金属进行转化。

Zalán 知道 (N) 种不同的金属，编号从：

$$1$$

到：

$$N$$

第 (i) 种金属的一块金属锭价值：

$$v_i$$

美元。

利用他的炼金术，Zalán 可以把：

$$c_i$$

块第 (i) 种金属锭，转化成：

$$1$$

块第 (i+1) 种金属锭。

不过，他还没有找到把第 (N) 种金属继续转化成更高级金属的方法。

---

每天，Zalán 都会从世界闻名的金属商人 Ea-nāṣir 那里收到一批金属锭。

一共有：

$$Q$$

天。

在第 (i) 天，他会收到：

$$a_i$$

块第：

$$b_i$$

种金属。

Zalán 的实验室比较狭小，因此：

每天结束时，他必须把手中所有剩余的金属锭全部卖掉。

---

由于 Zalán 已经提前知道未来每天会收到哪些货物，因此他想知道：

在第 (i) 天，从 (a_i) 块第 (b_i) 种金属开始，经过任意一系列炼金转化之后，他最终最多可以拥有价值多少美元的金属锭？

Zalán 正忙着进行金属转化，所以他请你编写一个程序，帮助他计算每一天的最大价值。

---

输入格式

第一行包含两个用空格分隔的整数：

N Q

第二行包含 (N) 个用空格分隔的整数：

v1 v2 ... vN

表示每种金属锭的价值。

第三行包含 (N-1) 个用空格分隔的整数：

c1 c2 ... cN-1

其中 (c_i) 表示：

需要 (c_i) 块第 (i) 种金属锭，才能转化成 1 块第 (i+1) 种金属锭。

接下来有 (Q) 行。

每行包含两个用空格分隔的整数：

ai bi

表示第 (i) 天，Zalán 会收到：

• (a_i) 块金属锭；
• 这些金属锭属于第 (b_i) 种金属。

---

输出格式

输出 (Q) 行。

每行输出一个整数，表示：

在第 (i) 天，如果 Zalán 从 (a_i) 块第 (b_i) 种金属开始，经过任意一系列转化后，他最终能够得到的最大总价值。

---

数据范围

$$2 \le N \le 100000$$ $$1 \le Q \le 100000$$

对于所有：

$$1 \le i \le N$$

都有：

$$1 \le v_i \le 10^9$$

对于所有：

$$1 \le i < N$$

都有：

$$1 \le c_i \le 9$$

对于所有：

$$1 \le i \le Q$$

都有：

$$1 \le a_i \le 10^9$$

以及：

$$1 \le b_i \le N$$

---

子任务

• 子任务 1（+14%）：

$$N=2$$

• 子任务 2（+10%）：

对于所有：

$$1 \le i < N$$

都有：

$$c_i=1$$

• 子任务 3（+26%）：

$$N,Q\le1000$$

• 子任务 4（+21%）：

对于所有：

$$1 \le i < N$$

都有：

$$c_i\ge2$$

• 子任务 5（+29%）：

没有额外限制。

---

注意事项

如果你使用的是对整数类型比较敏感的语言，例如：

• C++
• Java
• C

那么请务必使用 64 位整数类型，以避免整数溢出。

64 位整数类型包括：

• C / C++：long long
• C# / Java：long

如果你使用 Python，并且程序超过时间限制，可以尝试在提交时选择：

Python 3.11 (PyPy 7.3.19)

通常这样能够让程序运行得更快。

---

样例说明

样例 1

本样例中一共有 4 种金属，它们的价值分别为：

$$2,\ 3,\ 1,\ 7$$

美元。

Zalán 会在 3 天中收到不同批次的金属锭。

第 1、2、3 种金属的转化比例分别为：

$$2:1,\ 1:1,\ 2:1$$

也就是说：

• 2 块金属 1 → 1 块金属 2；
• 1 块金属 2 → 1 块金属 3；
• 2 块金属 3 → 1 块金属 4。

---

第 1 天

Zalán 收到：

$$3$$

块金属 1。

他可以直接全部卖掉，获得：

$$3\times2=6$$

美元。

---

第 2 天

他收到：

$$11$$

块金属 2。

其中，可以把：

$$10$$

块金属 2 转化为：

$$10$$

块金属 3。

然后，再把这 10 块金属 3 转化成：

$$5$$

块金属 4。

最终剩下：

• 1 块金属 2；
• 5 块金属 4。

总价值为：

$$1\times3+5\times7$$ $$=3+35$$ $$=38$$

美元。

---

第 3 天

Zalán 收到：

$$2$$

块金属 4。

第 4 种金属已经不能继续转化，因此直接出售：

$$2\times7=14$$

美元。

---

样例输入 1

4 3
2 3 1 7
2 1 2
3 1
11 2
2 4

样例输出 1

6
38
14

---

样例输入 2

2 1
3 4
1
6 1

样例输出 2

24