有 n 个球。它们排列成一排。每个球都有一个颜色(为了方便起见,一个整数)和一个整数值。第 i 个球的颜色是 ci,第 i 个球的值是 vi。
松鼠利斯选择一些球并在不改变球的相对顺序的情况下形成新的序列。她想要最大化这个序列的价值。
序列的值定义为每个球的以下值的总和(其中 a 和 b 是给定的常量):
- 如果球不在序列的开头并且球的颜色与前一个球的颜色相同,则添加(球的值) × a。
- 否则,添加(球的值) × b。
您有 q 个查询。每个查询包含两个整数 ai 和 bi。对于每个查询,找到当 a = ai 且 b = bi 时她可以生成的序列的最大值。
请注意,新序列可以为空,空序列的值定义为零。
输入
第一行包含两个整数 n 和 q (1 ≤ n ≤ 105; 1 ≤ q ≤ 500)。第二行包含 n 个整数:v1, v2, ..., vn (|vi| ≤ 105)。第三行包含 n 个整数:c1, c2, ..., cn (1 ≤ ci ≤ n)。
以下 q 行包含用于查询的常量 a 和 b 的值。这些行的第 i 行包含两个整数 ai 和 bi (|ai|, |bi| ≤ 105)。
在每一行中,整数之间用单个空格分隔。
输出
对于每个查询,输出一行包含一个整数 - 查询的答案。第 i 行包含输入顺序中第 i 个查询的答案。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
6 3 1 -2 3 4 0 -1 1 2 1 2 1 1 5 1 -2 1 1 0
输出 #1
20 9 4
输入 #2
4 1 -3 6 -1 2 1 2 3 1 1 -1
输出 #2
5
注意
在第一个示例中,要达到最大值:
- 在第一个查询中,您应该选择第 1、第 3 和第 4 个球。
- 在第二个查询中,您应该选择第 3、第 4、第 5 和第 6 个球。
- 在第三个查询中,您应该选择第二个和第四个球。
请注意,可能还有其他方法可以实现最大值。