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 2 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, \dots, 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~.

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 2 số nguyên ~N~ và ~Q~ (~1 \le N \le 100000, 1 \le Q \le 500~).
• Dòng thứ 2 chứa ~N~ số nguyên ~v_1, v_2, \dots, v_N~ (~|v_i| \le 100000~).
• Dòng thứ 3 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 2 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.

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