Wooden Sticks

View as PDF
Submit solution
Points: 0.22 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Taejon 2002
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

  • Thời gian chuẩn bị cho đoạn gỗ đầu tiên là ~1~ phút.
  • 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 \leq l'~ and ~w \leq 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 \leq 100~. Mỗi test gồm:

  • Dòng đầu là số nguyên dương ~N \leq 5000~.
  • Sau đó là ~N~ dòng gồm ~N~ cặp số nguyên dương ~(l_1,w_1),(l_2,w_2),\ldots,(l_N,w_N)~, ~l_i,w_i \leq 10000~, là độ dài và trọng lượng của các khối gỗ.

Output

In ra ~T~ dòng, mỗi dòng là thời gian ít nhất để chuẩn bị các đoạn gỗ của test đó.

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

Comments

Please read the guidelines before commenting.