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, … 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, \dots, 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 với độ dài bước nhảy và số điểm thưởng của bước nhảy đó. Nếu ~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 > 0~ thì Robot sẽ phải di chuyển từ vị trí hiện tại sang phải ~l_i~ vị trí; ~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.

Yêu cầu: Tìm tổng số điểm lớn nhất có thể đạt được thỏa mãn điều kiện bài toán.

Input

• Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ dữ liệu (~1 \le T \le 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~ (~1 \le N \le 200~).
  • Dòng thứ hai ghi ~N~ số nguyên ~l_1, l_2, \dots, l_N~ (~-200 \le l_i \le 200~).
  • Dòng thứ ba ghi ~N~ số nguyên dương ~p_1, p_2, \dots, p_N~ (~1 \le p_i \le 10^7~).

Output

• Với mỗi bộ dữ liệu, 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.

Sample Input 1

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

Sample Output 1

11
9