Cho \(n\) đồ vật, mỗi đồ vật có kích thước và giá trị lần lượt là \(<w_1,v_1>,<w_2,v_2>,..., <w_n,v_n>\), một ba lô có kích thước \(M\), hãy tìm cách xếp các đồ vật vào ba lô sao cho tổng kích thước các đồ vật không vượt quá kích thước của ba lô, mà tổng giá trị thu được là lớn nhất.

Giả sử rằng hình dạng của đồ vật và ba lô không ảnh hưởng tới việc xếp đồ, tức là cứ xếp thoải mái miễn là tổng kích thước các đồ vật xếp vào không vượt quá kích thước ba lô là được và chú ý rằng mỗi đồ vật chỉ có số lượng là \(1\) thôi nhé

Input

Dòng đầu chứa số đồ vật \(n (1 \le n \le 100)\)

Tiếp theo \(n\) dòng mỗi dòng chứa hai giá trị \(<w_i,v_i>\) tương ứng là kích thước và giá trị các đồ vật \((1 \le w_i, v_i \le 10^6)\)

Tiếp theo chứa số lần truy vấn \(q (1 \le q \le 10000)\)

Tiếp theo là \(q\) dòng mỗi dòng tương ứng với một kích thước ba lô cần truy vấn \(M (1 \le M \le 10^4)\)

Output

Gồm \(q\) dòng mỗi dòng tương ứng với tổng giá trị lớn nhất theo từng truy vấn

Ví dụ

Input

6
4 7
3 5
4 8
2 3
2 4
5 9
4
11
100
1
8

Output

21
36
0
15

Giải thích

test 1: \(M=11\) thì ta chọn đồ vật <4,8>, <2,4>, <5,9> tổng kích thước \(4+2+5=11\) tổng giá trị là \(8+4+9=21\)

test 2: \(M=100\) thì ta chọn tất cả các đồ vật tổng kích thước \(4+3+4+2+2+5=20\) tổng giá trị là \(7+5+8+3+4+9=36\)

test 3: \(M=1\) thì không chọn được đồ vật nào nên tổng kích thước là \(0\) và tổng giá trị là \(0\)

test 14: \(M=8\) thì ta chọn đồ vật <4,8>, <4,7> tổng kích thước \(4+4=8\) tổng giá trị là \(8+7=15\)