Bạn cùng với chú Robot vui nhộn của mình tham gia cuộc thi “Robot khiêu vũ”. Cuộc thi diễn ra trên một đường nằm ngang với các vị trí nguyên, biên trái là vị trí \(0\), tiếp theo là vị trí \(1\),\(\ldots\) và các vị trí được xem là vô hạn về phía bên phải. Mỗi Robot dự thi sẽ thực hiện một số bước nhảy, mỗi bước nhảy đơn giản chỉ di chuyển sang trái hoặc sang phải một số vị trí từ vị trí hiện tại.

Trước khi thực hiện cuộc thi, mỗi Robot tham gia sẽ được Ban giám khảo cung cấp một dãy gồm \(N\) bước nhảy \(M_1,\ M_2,\ldots,\ M_N\). Mỗi bước nhảy \(M_i\) gồm số nguyên \(l_i\) và số nguyên dương \(p_i\) tương ứng là độ dài bước nhảy và số điểm thưởng của bước nhảy đó.

• Nếu \(l_i\) âm (\(l_i< 0\)) thì Robot sẽ phải di chuyển từ vị trí hiện tại sang trái với độ dài bằng trị tuyệt đối của \(l_i\) vị trí;
• \(l_i\) dương (\(l_i> 0\)) thì Robot sẽ phải di chuyểntừ vị trí hiện tại sang phải \(l_i\) vị trí;
• \(l_i\) bằng \(0\) (\(l_i = 0\)) thì Robot đứng yên.

Kết thúc một bước nhảy, Robot dừng lại ở vị trí di chuyển đến sau cùng và đó cũng là vị trí xuất phát cho bước nhảy tiếp theo.

Bạn hãy chọn cho chú Robot của mình một số bước nhảy bằng cách chọn hoặc bỏ qua các bước nhảy theo thứ tự từ trái sang phải từ các bước nhảy nhận được từ Ban giám khảo sao cho, xuất phát từ vị trí \(0\), các bước nhảy được chọn không dẫn Robot di chuyển vượt qua biên tráiđường ngang và tổng số điểm thu được là lớn nhất.

Input

• Dòng đầu tiên ghi số nguyên dương \(T\) là số bộ dữ liệu có trong tệp (\(1\leq T\leq 200\)).
• Tiếp theo là \(T\) bộ dữ liệu, mỗi bộ bao gồm:
  • Dòng thứ nhất ghi số nguyên dương \(N\) là số bước nhảy được cho bởi Ban giám khảo (\(1\leq N\leq 200\));
  • Dòng thứ hai ghi \(N\) số nguyên \(l_1,\ l_2,\ldots,\ l_N\ (-200\leq l_i\leq 200,\ i = 1,\ 2,\ldots, N\));
  • Dòng thứ ba ghi \(N\) số nguyên dương \(p_1,\ p_2,\ldots,\ p_N (1\leq p_i\leq 10^7,\ i = 1,\ 2,\ldots,\ N\)).

Output

• Tương ứng với mỗi bộ dữ liệu trong tệp dữ liệu vào ghi ra một dòng gồm một số nguyên dương là tổng số điểm lớn nhất tìm được.

Ví dụ

Sample input

2
3
2 -4 6
4 5 7
4
0 4 -5 -3 
3 2 7 4

Sample output

11
9

Note

• Bộ dữ liệu \(1\): Chọn bước nhảy \(1\), Robot di chuyển từ vị trí \(0\) sang phải \(2\) vị trí, dừng lại tại vị trí \(2\). Tại vị trí \(2\) (bỏ qua bước nhảy \(2\) vì sẽ dẫn Robot vượt qua biên trái), chọn bước nhảy \(3\), Robot di chuyển đến vị trí \(8\) và kết thúc bài thi. Tổng điểm: \(4+7 = 11\).
• Bộ dữ liệu \(2\): Chọn các bước nhảy \(1,\ 2\) và \(4\). Tổng điểm: \(3+2+4 = 9\).