Mái che

Trên một trục số có $n$ đống thóc. Đống thứ $i$ nằm tại vị trí $x_i$ và có lượng thóc $v_i$. Nhiều đống thóc có thể cùng vị trí.

Một mái che là một đoạn đóng có độ dài $d$. Một đống thóc nằm trên mái che, kể cả tại hai đầu mút, được xem là được phủ. Trong mỗi truy vấn, bạn được đặt đúng $k$ mái che có cùng độ dài $d$. Nếu một đống thóc được nhiều mái che phủ thì lượng thóc của nó cũng chỉ được tính một lần.

Hãy tìm tổng lượng thóc lớn nhất có thể được phủ trong mỗi truy vấn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ $(1\le n\le {10}^5,1\le q\le 20)$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$ $(0\le x_i\le {10}^9)$.
• Dòng thứ ba chứa $n$ số nguyên $v_1,v_2,\dots ,v_n$ $(1\le v_i\le {10}^9)$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa hai số nguyên $k$ và $d$ $(1\le k\le n,0\le d\le {10}^9)$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng tổng lượng thóc lớn nhất có thể được phủ.

Ràng buộc

• $1\le n\le {10}^5$, $1\le q\le 20$.
• $0\le x_i\le {10}^9$, $1\le v_i\le {10}^9$.
• $1\le k\le n$, $0\le d\le {10}^9$.

Subtasks

• Subtask 1 ($50\%$ số điểm): $n\le 5000$.
• Subtask 2 ($50\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ