Дано n мячей, расставленных в ряд. У каждого мяча есть цвет (выраженный для удобства целым числом) и целочисленное значение. Цвет i-ого мяча равен ci, а значение i-ого мяча равно vi.
Белка Лисска выбирает несколько мячей и создает из них последовательность, не меняя относительный порядок мячей. Она хочет максимизировать значение этой последовательности.
Значение последовательности определяется как сумма следующих значений для каждого мяча (где a и b — заданные константы):
- Если мяч находится не в начале последовательности, а цвет у мяча такой же, как цвет предыдущего мяча, прибавьте (значение мяча) × a.
- В противном случае, прибавьте (значение мяча) × b.
Дано q запросов. Каждый запрос содержит два целых числа ai и bi. Для каждого запроса найдите максимальное значение последовательности, которую может построить белочка при a = ai и b = bi.
Заметьте, что созданная последовательность может быть пустой, а значение пустой последовательности считается равным нулю.
Выходные данные
Для каждого запроса выведите строку, содержащую одно целое число — ответ на запрос. В i-ой строке содержится ответ на i-ый запрос в порядке ввода.
Пожалуйста, не используйте спецификатор %lld, для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере, чтобы достичь максимальное значение:
- В первом запросе надо выбрать 1ый, 3ий и 4ый мяч.
- Во втором запросе надо выбрать 3ий, 4ый, 5ый и 6ой мячи.
- В третьем запросе нужно выбрать 2ой и 4ый мячи.
Заметьте, что могут быть и другие способы достичь максимальное значение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0
|
20
9
4
|
|
2
|
4 1
-3 6 -1 2
1 2 3 1
1 -1
|
5
|