Loli hiện đang sử dụng một con laptop cổ lô sĩ. Mặc dù Loli không dùng gì quá nặng, tuy nhiên laptop của Loli luôn bị tràn RAM. Loli không biết làm gì để có thêm RAM. "Hay là mình lên mạng để tải thêm RAM nhỉ?" - Loli thắc mắc.

Sau khi lên mạng, Loli đã tìm ra một trang web khá "uy tín". Trang web đó rao bán ~n~ phần mềm giúp tăng RAM trong máy. Cụ thể như sau:

• Phần mềm tăng RAM thứ ~i~ cần ~a_i~ GB RAM để chạy (chúng chỉ chạy lần đầu tiên, sau khi chạy xong, số RAM đó sẽ được giải phóng để Loli làm việc khác).
• Sau khi chạy phần mềm thứ ~i~, máy của Loli sẽ được tăng thêm ~b_i~ GB RAM (tăng vĩnh viễn).

Mỗi phần mềm chỉ được mua một lần. Tại một thời điểm chỉ được dùng nhiều nhất một phần mềm. Laptop của Loli hiện tại chỉ có ~k~ GB RAM (Loli chưa mua phần mềm nào).

Vì nhà của Loli quá giàu nên Loli tất nhiên có thể mua hết đống phần mềm này. Dĩ nhiên, nếu phần mềm nào yêu cầu nhiều RAM hơn số lượng RAM máy Loli đang có thì phần mềm đó không thể chạy được.

Loli ngây thơ tin vào những quảng cáo sặc mùi scam đó. Bạn của Loli là Lilo sau khi nghe những lời Loli nói thì cười sặc hết cả nước mũi. Lilo thừa biết đó không phải là sự thật, tuy nhiên thay vì bảo Loli thì Lilo lại nhờ bạn làm một chương trình để tìm cách mua và sử dụng các phần mềm sao cho máy của Loli có lượng RAM là lớn nhất có thể.

Hỏi lượng RAM lớn nhất có thể là bao nhiêu?

Input

• Dòng đầu chứa số nguyên ~T\ (1\le T\le 50)~ là số lượng test nhỏ.
• Sau đó là các test nhỏ:
  • Dòng đầu của mỗi test nhỏ chứa hai số nguyên ~n~ và ~k~ ~(1\le n \le 5000,\ 1\le k\le 5000)~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~a_i\ (1\le a_i\le 5000)~.
  • Dòng cuối cùng chứa ~n~ số nguyên ~b_i\ (1\le b_i\le 5000)~.

Output

• Mỗi dòng chứa một số nguyên là kết quả của test nhỏ tương ứng.

Sample Input 1

4
5 1
1 1 1 5 1
1 1 1 1 1
3 10
30 20 10
100 9 10
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 8 16 32
128 64 8 16 32

Sample Output 1

6
29
1
256

Giải thích

• Ở test nhỏ đầu tiên, sử dụng lần lượt phần mềm thứ ~1, 2, 3, 5~ để tăng lượng RAM thành ~5~ GB, sau đó dùng phần mềm ~4~ để tăng lên thành ~6~ GB.
• Ở test nhỏ thứ hai, Loli chỉ có đủ RAM để chạy phần mềm thứ ~3~, sau khi dùng nó, Loli sẽ có ~20~ GB RAM, đủ để chạy phần mềm thứ ~2~ để tăng lên thành ~29~ GB. Tuy nhiên phần mềm thứ ~1~ cần tới ~30~ GB RAM, vì vậy phần mềm thứ ~1~ không chạy được, đáp án cuối là ~29~ GB RAM.
• Ở test nhỏ thứ ba, mọi phần mềm đều cần hơn ~1~ GB RAM để chạy, vì vậy Loli không chạy được phần mềm nào, đáp án cuối là ~1~ GB RAM.

Ràng buộc

• 30% số điểm có ~n \le 10~.
• 40% số điểm có ~n \le 1000~.
• 30% số điểm còn lại không có ràng buộc gì thêm.