Đồ thị Descartes là một khái niệm không xa lạ với mọi người. Chắc hẳn trong những năm tháng THCS, khi là những cô bé, cậu bé mới lớn, chúng ta đã làm việc rất nhiều với đồ thị này.

Đồ thị Descartes được đặt theo tên của nhà toán học và triết học người Pháp René Descartes ($1596-1650$). Ông được biết đến với câu nói nổi tiếng "Cogito, ergo sum" (Tôi tư duy, vậy tôi tồn tại). Descartes không chỉ đóng góp cho triết học mà còn có những phát minh quan trọng trong lĩnh vực toán học. Hệ tọa độ Descartes, nền tảng của đồ thị này, được ông phát triển, giúp kết nối giữa hình học và đại số.

Hôm nay bạn X quyết định thực hiện một cuộc phiêu lưu trên đồ thị này!

Cho $n$ điểm trên mặt phẳng.
X muốn tìm đường đi dài nhất thoả mãn điều kiện sau để thực hiện cuộc phiêu lưu:

Đầu tiên xuất phát tại $1$ điểm bất kì
Trong $1$ bước nếu đang đứng tại ô $(x, y)$ có thể đi sang $(a, b)$ nếu $x \leq a$ và $y \leq b$

Hãy tìm độ dài đó nhé!

4 
1 2
2 5
3 3
4 4

3