MSTICK - Wooden Sticks

Giới hạn

• Thời gian: 0.328s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Có n đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị :

(a) Thời gian chuẩn bị cho đoạn gỗ đầu tiên là 1 phút.

(b) Sau khi xử lý xong đoạn gỗ có chiều dài l và trọng lượng w, không mất thời gian xử lý nếu đoạn gỗ tiếp theo có độ dài l' và trọng lượng w' thỏa l ≤ l' and w ≤ w'. Ngược lại mất 1 phút để chuẩn bị.

 

Tìm thời gian chuẩn bị ít nhất cho n đoạn gỗ.

Ví dụ có 5 đoạn ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , và ( 4 , 1 ), thì thời gian ít nhất là 2 vì có thể xử lý theo thứ tự như sau ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

Input

Dòng đầu là số lượng test, T. Mỗi test gồm 2 dòng:

• Dòng đầu là số n , 1 <= n <= 5000 ,
• Dòng thứ hai gồm 2n số nguyên dương l1 , w1 , l2 , w2 ,..., ln , wn <= 10000, li và wi là độ dài và trọng lượng của đoạn gỗ thứ i. 

 

Output

Ghi ra thời gian ít nhất trên từng dòng.
​
SAMPLE INPUT
3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

SAMPLE OUTPUT
2
1
3

---

• Người up: vdmedragon
• Nguồn bài: Taejon 2002