CF264C Choosing Balls

有 $n$ 个小球，这些小球排成一行。每个小球有一个颜色（用整数表示，便于处理）和一个整数权值。第 $i$ 个小球的颜色为 $c_i$，权值为 $v_i$。 松鼠 Liss 会选择若干个小球，组成一个新的序列，要求不改变原有小球的相对顺序。她想让新序列的价值最大。 新序列的价值定义为：对每个小球（给定常数 $a$ 和 $b$，下称 $a$ 和 $b$），按照如下规则计算： - 如果这个小球不是该序列的第一个小球，并且颜色与前一个小球相同，则将该小球的权值乘以 $a$ 加入总价值。 - 否则，将该小球的权值乘以 $b$ 加入总价值。 你将得到 $q$ 个询问。每个询问包含两个整数 $a_i$ 和 $b_i$。对于每个询问，当 $a=a_i$ 且 $b=b_i$ 时，请求出能够得到的序列的最大价值。 注意，新序列可以为空，空序列的价值定义为 $0$。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$；$1 \leq q \leq 500$）。 第二行包含 $n$ 个整数：$v_1, v_2, \ldots, v_n$（$|v_i| \leq 10^5$）。 第三行包含 $n$ 个整数：$c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq n$）。 接下来 $q$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$|a_i|, |b_i| \leq 10^5$）。 所有整数之间用单个空格分隔。

对于每个询问，输出一行一个整数，表示该询问对应的最大序列价值。第 $i$ 行对应输入中的第 $i$ 个询问。 请不要在 C++ 中使用 %lld 读写 64 位整数，建议使用 cin、cout 流或 %I64d。

在第一个样例中，为了获得最大价值： - 第一个询问应选择第 1、3 和 4 个小球。 - 第二个询问应选择第 3、4、5 和 6 个小球。 - 第三个询问应选择第 2 和 4 个小球。 注意，也可能存在其他获得最大价值的选择方式。 由 ChatGPT 5 翻译