Có ~N~ quả bóng được đánh chỉ số từ ~1~ tới ~N~. Quả bóng ~i~ có màu là ~c_i~ và giá trị là ~v_i~.

Cho hai số nguyên ~a, b~. Bạn cần chọn ra ~k~ (~k~ bất kỳ) quả bóng có chỉ số ~i_1, i_2, \dots, i_k~ ~(1 \le i_1 < i_2 < \dots < i_k \le N)~, xếp chúng thành một hàng trong đó quả bóng ~i_1~ đặt ở đầu hàng (bên trái nhất), quả bóng ~i_2~ đặt ở thứ hai hàng, ..., quả bóng ~i_k~ được đặt cuối hàng (bên phải nhất). Định nghĩa giá trị của hàng gồm ~k~ bóng này là một số nguyên ~S~ bằng tổng của các giá trị sau:

• Nếu một quả bóng không nằm ở đầu hàng và có màu giống hệt màu của quả bóng ngay bên trái nó trong hàng, cộng vào ~S~ giá trị của quả bóng đó nhân với ~a~;

• Ngược lại, cộng vào ~S~ giá trị của quả bóng đó nhân với ~b~.

Trường hợp ~k=0~ thì ~S=0~.

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn bạn được cho biết giá trị của ~a~ và ~b~. Nhiệm vụ của bạn là xác định và in ra giá trị lớn nhất có thể của ~S~ cho mỗi truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N \le 100000, 1 \le Q \le 500)~;

• Dòng thứ hai chứa ~N~ số nguyên ~v_1, v_2, \dots, v_N~ ~(|v_i| \le 100000)~;

• Dòng thứ ba chứa ~N~ số nguyên ~c_1, c_2, \dots, c_N~ ~(1 \le c_i \le N)~;

• ~Q~ dòng sau, mỗi dòng gồm hai số nguyên ~a, b~ mô tả một truy vấn ~(|a|, |b| \le 100000)~.

Output

Với mỗi truy vấn, in ra giá trị lớn nhất của ~S~ trên một dòng.

Scoring

Sample Input 1

6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0

Sample Output 1

20
9
4

Sample Input 2

4 1
-3 6 -1 2
1 2 3 1
1 -1

Sample Output 2

5

Notes

• Truy vấn ~1~: Chọn bóng ~1, 3, 4~;

• Truy vấn ~2~: Chọn bóng ~3, 4, 5, 6~;

• Truy vấn ~3~: Chọn bóng ~2, 4~.