Đội bay cho thuê

Một công ty vận tải có đúng một chiếc trực thăng để cho thuê. Công ty nhận trước \(n\) hợp đồng; hợp đồng thứ \(i\) bắt đầu ở thời điểm \(st_i\), kéo dài \(d_i\) đơn vị thời gian (chiếm khoảng \([st_i, st_i + d_i)\)) và sinh ra doanh thu \(p_i\). Hai hợp đồng có thể cùng thực hiện nếu hợp đồng sau bắt đầu không sớm hơn thời điểm kết thúc của hợp đồng trước; hợp đồng có \(d_i = 0\) không chiếm thời gian.

Hãy chọn tập hợp đồng thực hiện được để tổng doanh thu lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm dòng chứa \(n\), tiếp theo là \(n\) dòng, mỗi dòng ba số nguyên \(st_i\), \(d_i\), \(p_i\).

Output

Với mỗi bộ test in ra một dòng chứa doanh thu lớn nhất.

Constraints

• \(1 \le T \le 10\)
• \(1 \le n \le 10^5\)
• \(0 \le st_i, d_i, p_i \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ộ đầu, chọn các khoảng \([2,6)\), \([6,6)\), \([6,8)\) với doanh thu \(7 + 3 + 6 = 16\). Ở bộ hai, chọn \([3,4)\), \([4,4)\), \([4,6)\) với doanh thu \(2 + 1 + 9 = 12\).