Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mstick

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 , 
và 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.
 
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 

Output

 

Ghi ra thời gian ít nhất trên từng dòng.
SAMPLE OUTPUT
2
1
3