Có ~n~ quả bóng được đánh số thứ tự từ ~1~ đến ~n~. Chúng được sắp xếp thành một dãy dài, quả bóng thứ ~i~ có một màu ~c_i ~ (biểu diễn như là số nguyên) và có giá trị ~v_i~.

Liss chọn ra một vài quả bóng và tạo thành một dãy mới mà không làm thay đổi thứ tự tương ứng của các quả bóng trong dãy ban đầu (tức là quả bóng thứ ~i~ đứng trước quả ~j~ trong dãy ban đầu thì trong dãy mới ~i~ vẫn đứng trước ~j~). Cô ấy muốn giá trị của các quả bóng được chọn là lớn nhất.

Giá trị của dãy được tính như là tổng giá trị của mỗi quả bóng theo cách sau: (~a~, ~b~ là các hằng số nguyên cho trước):

• Nếu quả bóng không ở vị trí đầu tiên của dãy và màu của quả bóng cùng màu với quả trước ta thêm vào: (giá trị quả bóng) ~ \times  a~.

• Ngược lại ta thêm vào: (giá trị quả bóng)~ \times b~.

Bạn được cho ~q~ truy vấn, mỗi truy vấn chứa hai số nguyên ~a_i~ và ~ b_i~.

Yêu cầu

Với mỗi truy vấn tìm giá trị lớn nhất của dãy mà Liss nhận được khi ~a = a_i~ và ~b = b_i~

Dữ liệu vào

Dòng ~1~ chứa hai số nguyên ~n~ và ~q~ (~1 \leq n \leq 10^5; 1 \leq q \leq 500~).

Dòng ~2~ chứa ~n~ số nguyên: ~ v_1, v_2, ..., v_n~ (~ \left | v_i \right | \leq 10^5~).

Dòng ~3~ chứa ~n~ số nguyên: ~ c_1, c_2, ... , c_n~ (~1 \leq  c_i  \leq n~).

~q~ dòng sau, mỗi dòng chứa hai giá trị ~a~ và ~b~. Dòng thứ ~i~ chứa hai số nguyên ~a_i ~ và ~b_i ~ (~ \left | a_i \right | , \left | b_i \right | \leq 10^5~).

Các số trên mỗi dòng cách nhau ít nhất một dấu cách đơn.

Kết quả ra

Mỗi dòng chứa một số nguyên – kết quả của mỗi truy vấn. Dòng thứ ~i~ chứa kết quả của truy vấn thứ ~i~ theo đúng thứ tự như trong tệp dữ liệu vào.

Sample Input

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

Sample Output

20
9
4

Chú ý:

~30\%~ số test ứng với ~30\%~ số điểm có ~n \leq 20~

~60\% ~ số test ứng với ~60\%~ số điểm có ~n \leq 10000~

Nguồn: Trường THPT Chuyên Lê Hồng Phong-Nam Định