Tập đoàn

Tập đoàn DEPTRAI là một công ty nhỏ sở hữu một chiếc máy bay. Khách hàng của công ty là các công ty hàng không thuê máy bay để đáp ứng tình trạng quá tải thường xuyên.

 Khách hàng gửi đơn đặt hàng thuê bao gồm một khoảng thời gian và giá mà khách hàng sẵn sàng trả cho việc thuê máy bay trong khoảng thời gian nhất định. Đơn đặt hàng của tất cả các khách hàng được biết trước. Tất nhiên, không phải tất cả các đơn đặt hàng đều có thể được cung cấp và một số đơn đặt hàng phải bị từ chối. Huy là giám đốc của công ty muốn tối đa hóa lợi nhuận của công ty. Bạn được Huy yêu cầu tính toán một giải pháp tối ưu nhất khi cho thuê các máy bay của công ty.

 Ví dụ: xem xét trường hợp công ty có $4$ đơn đặt hàng:


      + Đơn hàng $1$ (thời gian bắt đầu $1$, thời gian $5$, giá $10$)


      + Đơn hàng $2$ (thời gian bắt đầu $3$, thời gian $7$, giá $8$)


      + Đơn hàng $3$ (thời gian bắt đầu $5$, thời gian $9$, giá $9$)


      + Đơn hàng $4$ (thời gian bắt đầu $6$, thời gian $9$, giá $8$)

 Giải pháp tối ưu bao gồm cho thuê đơn hàng $1$ và $4$ và mức doanh thu là $10 + 8 = 18$. Trong ví dụ này nếu chọn đơn hàng $1$ thì không thể chọn đơn hàng $3$ vì bị trùng thời gian.

Input

Dòng đầu tiên của đầu vào chứa số \(T ≤ 10\) cho biết số lượng trường hợp kiểm tra.
Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa số lượng đơn hàng \(n (n ≤ 5000)\).
Trong n dòng sau đây các đơn đặt hàng được đưa ra. Mỗi đơn hàng được mô tả bởi \(3\) giá trị nguyên: Thời gian bắt đầu của đơn hàng \(st (0 ≤ st ≤ 10^9)\), thời lượng \(d\) của đơn hàng \((0 ≤ d ≤ 10^9)\) và tiền thuê \(p\) \((0 ≤ p ≤ 10^9)\).

Output

Bạn được yêu cầu tính toán một giải pháp tối ưu. Đối với mỗi trường hợp thử nghiệm, chương trình của bạn phải ghi tổng tiền lớn nhất mà công ty thu được.

Example

Test 1

Input

Output

18
15

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận