C. Выбираем мячи
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дано 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.

Примеры
Входные данные
6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0
Выходные данные
20
9
4
Входные данные
4 1
-3 6 -1 2
1 2 3 1
1 -1
Выходные данные
5
Примечание

В первом примере, чтобы достичь максимальное значение:

  • В первом запросе надо выбрать 1ый, 3ий и 4ый мяч.
  • Во втором запросе надо выбрать 3ий, 4ый, 5ый и 6ой мячи.
  • В третьем запросе нужно выбрать 2ой и 4ый мячи.

Заметьте, что могут быть и другие способы достичь максимальное значение.