Cho thuê máy bay

Hãng SẮN CORP có duy nhất một chiếc máy bay cho thuê. Có \(n\) đơn đặt thuê, mỗi đơn cho biết thời điểm bắt đầu \(st\), thời lượng \(d\) (đơn chiếm khoảng thời gian \([st, st+d)\)) và số tiền \(p\) khách sẵn sàng trả. Máy bay chỉ phục vụ một đơn tại một thời điểm: hai đơn được chọn cùng nhau nếu đơn này bắt đầu không sớm hơn thời điểm kết thúc \(st + d\) của đơn kia. Đơn có \(d = 0\) vẫn được tính là hợp lệ và không chiếm chỗ của ai.

Hãy chọn các đơn để tổng số tiền thu về lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test: một dòng chứa \(n\), rồi \(n\) dòng, mỗi dòng ba số nguyên \(st\), \(d\), \(p\).

Output

Với mỗi bộ test in ra một dòng là tổng tiền lớn nhất.

Constraints

• \(1 \le T \le 10\)
• \(1 \le n \le 5000\)
• \(0 \le st, d, p \le 10^9\)

Sample Input

2
5
2 4 7
3 3 5
6 2 6
5 1 4
6 0 3
3
4 2 9
4 0 1
3 1 2

Sample Output

16
12

Explanation

Bộ thứ nhất: chọn đơn \([2,6)\) giá \(7\), đơn \([6,6)\) giá \(3\) (độ dài \(0\)) và đơn \([6,8)\) giá \(6\), tổng \(16\). Bộ thứ hai: chọn \([3,4)\) giá \(2\), \([4,4)\) giá \(1\) và \([4,6)\) giá \(9\), tổng \(12\).