Phạt tốc độ

Lái xe vượt quá tốc độ cho phép là nguyên nhân của nhiều tai nạn giao thông nghiêm trọng. Việc đặt các camera đo tốc độ cũng đã hạn chế một phần lỗi vượt quá tốc độ cho phép. Tuy vậy một số người đã đối phó bằng cách giảm tốc độ ở nơi có camera và sau đó lại phóng nhanh. Để kiểm soát tốc độ chung trên toàn tuyến đường, người ta đặt camera ghi nhận thời điểm xe đi vào tuyến và thời điểm xe rời khỏi tuyến, sau đó dựa vào thời gian đi trên toàn tuyến để xác định mức phạt.

Xét một tuyến đường gồm $n$ đoạn. Đoạn thứ $i$ có độ dài $l_i$ và tốc độ tối đa cho phép là $v_i$ $(1\le i\le n)$.

Gọi $e$ là độ vượt quá tốc độ cho phép lớn nhất trên toàn tuyến, tức là giá trị lớn nhất của hiệu giữa tốc độ đi và tốc độ tối đa cho phép trên mỗi đoạn. Nếu $e>0$, người lái xe bị phạt theo các mức sau:

• Nếu $0<e\le a_1$ thì mức phạt là $f_1$ đồng;
• Nếu $a_1<e\le a_2$ thì mức phạt là $f_2$ đồng;
• Nếu $a_2<e\le a_3$ thì mức phạt là $f_3$ đồng;
• $\dots$
• Nếu $a_{m-2}<e\le a_{m-1}$ thì mức phạt là $f_{m-1}$ đồng;
• Nếu $a_{m-1}<e$ thì mức phạt là $f_m$ đồng.

Nếu $e\le 0$ thì người lái xe không bị phạt.

Hiện có số liệu chưa xử lý của $q$ xe. Xe thứ $i$ đi vào tuyến tại thời điểm $s_i$ và rời khỏi tuyến tại thời điểm $t_i$ $(1\le i\le q)$.

Yêu cầu: Với mỗi xe, hãy xác định mức phạt lớn nhất chắc chắn đúng về lỗi tốc độ, tức là mức phạt mà xe phải nộp với mọi cách đi trên các đoạn khớp với thời gian đã ghi nhận.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ $(1\le n\le 10)$.
• Dòng thứ hai chứa $n$ số nguyên $v_1,v_2,\dots ,v_n$ $(1\le v_i\le {10}^9)$.
• Dòng thứ ba chứa $n$ số nguyên $l_1,l_2,\dots ,l_n$ $(1\le l_i\le {10}^9)$.
• Dòng thứ tư chứa số nguyên $m$ $(1\le m\le {10}^5)$.
• Dòng thứ năm chứa $m-1$ số nguyên tăng dần $a_1,a_2,\dots ,a_{m-1}$ $(1\le a_i\le {10}^9)$. Nếu $m=1$ thì dòng này rỗng.
• Dòng thứ sáu chứa $m$ số nguyên tăng dần $f_1,f_2,\dots ,f_m$ $(1\le f_i\le {10}^9)$.
• Dòng thứ bảy chứa số nguyên $q$ $(1\le q\le {10}^5)$.
• Dòng thứ $i$ trong $q$ dòng tiếp theo chứa hai số nguyên $s_i$ và $t_i$ $(1\le s_i<t_i\le {10}^9)$.

Dữ liệu ra

In ra $q$ số nguyên, mỗi số trên một dòng, là số tiền phạt mà mỗi xe phải nộp (in $0$ nếu xe không bị phạt).

Dữ liệu bảo đảm rằng nếu $s_i$ và $t_i$ thay đổi không quá ${10}^{-5}$ thì số tiền phạt không thay đổi.

Ràng buộc

• $1\le n\le 10$; $1\le v_i,l_i\le {10}^9$.
• $1\le m\le {10}^5$; $1\le a_1<a_2<\dots <a_{m-1}\le {10}^9$; $1\le f_1<f_2<\dots <f_m\le {10}^9$.
• $1\le q\le {10}^5$; $1\le s_i<t_i\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $m\le {10}^2$, $q\le {10}^2$.
• Subtask 2 ($30\%$ số điểm): $m\le {10}^2$, $q\le {10}^5$.
• Subtask 3 ($40\%$ số điểm): $m\le {10}^5$, $q\le {10}^5$.

Ví dụ