Bessie có \(N\) công việc (\(1\leq N\leq 2\cdot 10^5\)) mà bạn có thể lựa chọn hoàn thành. Nếu chọn hoàn thành công việc thứ \(i\), bạn phải bắt đầu nó vào hoặc trước thời điểm \(s_i\) và cần \(t_i\) đơn vị thời gian để hoàn thành (\(0\leq s_i\leq 10^{18}\), \(1\leq t_i\leq 10^{18}\)).

Số công việc tối đa bạn có thể hoàn thành là bao nhiêu? Thời gian bắt đầu từ \(0\). Sau khi bắt đầu một công việc, bạn phải làm liên tục đến khi hoàn thành và không được bắt đầu công việc nào khác trong lúc đó.

Dữ liệu vào

Dòng đầu chứa \(T\), số bộ test độc lập (\(1\leq T\leq 10\)). Mỗi bộ test có định dạng như sau.

Dòng đầu chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\). Dòng thứ \(i+1\) chứa thông tin của công việc thứ \(i\).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(3\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng mới số công việc tối đa bạn có thể hoàn thành.

Phân nhóm

• Test 2: Trong cùng một bộ test, tất cả \(t_i\) bằng nhau.
• Các test 3–4: \(N\leq 2000\), \(s_i,t_i\leq 2000\).
• Các test 5–8: \(N\leq 2000\).
• Các test 9–16: Không có ràng buộc bổ sung.

Ví dụ

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2

1
2
2

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Job Completion

Tác giả: Benjamin Qi.