Bài tập

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\).

Sắn nghi ngờ rằng voi càng nặng thì chưa chắc càng thông minh. Để kiểm chứng, Sắn thu thập dữ liệu về một đàn voi và muốn chọn ra một nhóm voi đông nhất có thể, sao cho khi xếp chúng theo thứ tự thì cân nặng tăng dần thật sự (nghiêm ngặt) còn chỉ số IQ giảm dần thật sự (nghiêm ngặt).

Hãy giúp Sắn tìm số lượng voi lớn nhất và in ra một nhóm như vậy.

Nếu có nhiều nhóm có cùng số lượng lớn nhất, hãy in ra nhóm mà dãy số thứ tự (viết theo thứ tự chuỗi từ nhẹ đến nặng) là nhỏ nhất theo thứ tự từ điển.

Input

• Mỗi dòng mô tả một con voi bằng hai số nguyên: cân nặng \(w\) (đơn vị mg) và chỉ số IQ \(q\).
• Dữ liệu kết thúc bằng một dòng chứa số \(0\).
• Các con voi được đánh số từ \(1\) theo thứ tự xuất hiện. Hai con voi có thể trùng cả cân nặng lẫn IQ.

Output

• Dòng thứ nhất: số lượng voi lớn nhất \(k\).
• Dòng thứ hai: \(k\) số thứ tự các con voi được chọn, theo thứ tự cân nặng tăng dần (IQ giảm dần), cách nhau một dấu cách.

Constraints

• Có tối đa \(5000\) con voi (ít nhất một con).
• \(1 \le w, q \le 100000\)

Sample Input

3000 900
2000 1500
4500 700
2500 1400
5000 600
3500 1100
1000 2000
0

Sample Output

6
7 2 4 1 3 5

Explanation

Chọn các voi \(7, 2, 4, 1, 3, 5\) có cân nặng \(1000 < 2000 < 2500 < 3000 < 4500 < 5000\) và IQ \(2000 > 1500 > 1400 > 900 > 700 > 600\). Không thể chọn được \(7\) con.

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Hãy tìm một dãy con tăng nghiêm ngặt dài nhất, tức là dãy các chỉ số \(i_1 < i_2 < \dots < i_k\) với \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) và \(k\) lớn nhất.

Để đáp án là duy nhất, trong số các dãy chỉ số tối ưu hãy chọn dãy nhỏ nhất theo thứ tự từ điển (so sánh \(i_1\) trước, nếu bằng nhau thì so sánh \(i_2\), ...).

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

• Dòng thứ nhất: độ dài \(k\) của dãy con tăng dài nhất.
• Dòng thứ hai: \(k\) chỉ số \(i_1, i_2, \dots, i_k\) (đánh số từ \(1\), theo thứ tự tăng dần) của dãy chỉ số nhỏ nhất theo thứ tự từ điển.

Constraints

• \(1 \le N \le 5000\)
• \(|A_i| \le 10^9\)

Sample Input

7
4 -2 7 7 0 9 3

Sample Output

3
1 3 6

Explanation

Độ dài lớn nhất là \(3\). Các dãy chỉ số tối ưu gồm \((1,3,6)\), \((1,4,6)\), \((2,3,6)\), \((2,4,6)\), \((2,5,6)\), ...; dãy \((1,3,6)\) nhỏ nhất theo thứ tự từ điển.

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Hãy tìm một dãy con tăng nghiêm ngặt dài nhất, tức là dãy các chỉ số \(i_1 < i_2 < \dots < i_k\) với \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) và \(k\) lớn nhất.

Để đáp án là duy nhất, trong số các dãy chỉ số tối ưu hãy chọn dãy nhỏ nhất theo thứ tự từ điển (so sánh \(i_1\) trước, nếu bằng nhau thì so sánh \(i_2\), ...).

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

• Dòng thứ nhất: độ dài \(k\) của dãy con tăng dài nhất.
• Dòng thứ hai: \(k\) chỉ số \(i_1, i_2, \dots, i_k\) (đánh số từ \(1\), theo thứ tự tăng dần) của dãy chỉ số nhỏ nhất theo thứ tự từ điển.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(|A_i| \le 10^9\)

Sample Input

7
8 3 -5 3 6 4 10

Sample Output

4
3 4 5 7

Explanation

Độ dài lớn nhất là \(4\). Có hai dãy chỉ số tối ưu là \((3,4,5,7)\) ứng với \(-5,3,6,10\) và \((3,4,6,7)\) ứng với \(-5,3,4,10\); dãy đầu nhỏ hơn theo thứ tự từ điển.