鐘凡常常忘記寄收據，惹得黃于軒爆氣。
黃于軒每次催鐘凡都會有一個爆氣值 \(x_i\)；鐘凡拖延收據會有一個樂趣值 \(y_i\) 。
當鐘凡拖延收據到第 \(i\) 次時，他會得到 \(y_1+y_2+...+y_{i}\) 的樂趣，但黃于軒會有 \(x_1+x_2+...+x_{i}\) 的爆氣。
作為第三方公正人，Choder可以強制鐘凡馬上寄出收據，但是馬上寄出又對鐘凡來說太不公平了，因此他希望取得一個平衡。
然而Choder是偏心的，他評斷鐘凡的可愛度是 \(a\)，他會希望找到一個時間 \(k (0\leq k\leq n)\)，使得 \(a(y_1+y_2+...+y_{k})-(x_1+x_2+...+x_{k})\) 盡可能大。
他的心意隨時會改變，所以想問你 \(Q\) 次，給你 \(a\)，問這個最大值是多少。

Input

輸入第一行是一個 \(n\)。
接著是 \(n\) 行，每行兩個數字 \(x_i,y_i\)。
接著有一個 \(Q\)，代表詢問數。
接著一行有 \(Q\) 個數\(a\)。

Output

對於每個詢問，輸出一行一個整數代表答案。

Constraints

第 \(1\) 組測資，\(n=1\)，\(Q\leq 10\)。

第 \(2\) 組測資，\(n\leq 10\)，\(Q\leq 10\)。

第 \(3\) 組測資，\(n\leq 100\)，\(Q\leq 100\)。

第 \(4\) 組測資，\(n\leq 10^5\)，\(Q=1\)。

第 \(5\) 組測資，\(n\leq 10^5\)，\(Q\leq 10^5\)。

對於所有測資，\(1\leq x_i,y_i,a\leq 10^6\)。

Sample Input

5
10 2
5 3
8 1
9 6
4 3
5
1 2 3 4 5

Sample Output

0
0
9
24
39