CF264C.Choosing Balls

There are n balls. They are arranged in a row. Each ball has a color (for convenience an integer) and an integer value. The color of the i-th ball is c__i and the value of the i-th ball is v__i.

Squirrel Liss chooses some balls and makes a new sequence without changing the relative order of the balls. She wants to maximize the value of this sequence.

The value of the sequence is defined as the sum of following values for each ball (where a and b are given constants):

• If the ball is not in the beginning of the sequence and the color of the ball is same as previous ball's color, add (the value of the ball)  ×  a.
• Otherwise, add (the value of the ball)  ×  b.

You are given q queries. Each query contains two integers a__i and b__i. For each query find the maximal value of the sequence she can make when a = a__i and b = b__i.

Note that the new sequence can be empty, and the value of an empty sequence is defined as zero.

有 $n$ 个球，它们排成一行。每个球有一个颜色（为方便起见，用一个整数表示）和一个整数值。第 $i$ 个球的颜色为 $c_i$，值为 $v_i$。

松鼠 Liss 从中选出若干个球，组成一个新的序列，且不改变这些球在原序列中的相对顺序。她希望使该序列的“价值”最大化。

该序列的价值定义如下（其中 $a$ 和 $b$ 是给定的常数）：对序列中每个球，按以下规则累加贡献：

• 若该球不是序列的第一个球，且其颜色与前一个球的颜色相同，则加上（该球的值）$\times\, a$；
• 否则，加上（该球的值）$\times\, b$。

现在给出 $q$ 个查询，每个查询包含两个整数 $a_i$ 和 $b_i$。对每个查询，请计算当 $a = a_i$、$b = b_i$ 时，Liss 能构造出的最大序列价值。

注意：新序列可以为空，空序列的价值定义为 $0$。

The first line contains two integers n and q (1 ≤ n ≤ 105; 1 ≤ q ≤ 500). The second line contains n integers: _v_1, _v_2, ..., v__n (|v__i| ≤ 105). The third line contains n integers: _c_1, _c_2, ..., c__n (1 ≤ c__i ≤ n).

The following q lines contain the values of the constants a and b for queries. The i-th of these lines contains two integers a__i and b__i (|a__i|, |b__i| ≤ 105).

In each line integers are separated by single spaces.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$；$1 \leq q \leq 500$）。
第二行包含 $n$ 个整数：$v_1,\,v_2,\,\dots,\,v_n$（$|v_i| \leq 10^5$）。
第三行包含 $n$ 个整数：$c_1,\,c_2,\,\dots,\,c_n$（$1 \leq c_i \leq n$）。

接下来的 $q$ 行每行给出一次查询所用的常数 $a$ 和 $b$。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$|a_i|,\,|b_i| \leq 10^5$）。

每行中的整数均以单个空格分隔。

For each query, output a line containing an integer — the answer to the query. The i-th line contains the answer to the i-th query in the input order.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

对于每个查询，输出一行包含一个整数——该查询的答案。第 $i$ 行包含输入中第 $i$ 个查询的答案（按输入顺序）。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin、cout 流，或 %I64d 格式说明符。

In the first example, to achieve the maximal value:

• In the first query, you should select 1st, 3rd, and 4th ball.
• In the second query, you should select 3rd, 4th, 5th and 6th ball.
• In the third query, you should select 2nd and 4th ball.

Note that there may be other ways to achieve the maximal value.

在第一个例子中，为达到最大值：

• 在第一次查询中，应选择第 1、第 3 和第 4 个球。
• 在第二次查询中，应选择第 3、第 4、第 5 和第 6 个球。
• 在第三次查询中，应选择第 2 和第 4 个球。

注意：可能存在其他方式达到最大值。