id="a-graph-with-lines-and-dots-description-automatically-generatedđường-gấp-khúc-lizigzag.">Đường gấp khúc (lizigzag.*)

Trên mặt phẳng tọa độ Oxy cho n điểm A₁, A₂, …, A_n có tọa độ nguyên dương. Người ta muốn vẽ một đường gấp khúc (theo dạng răng cưa) bắt đầu từ gốc tọa độ. Như vậy dãy điểm của đường gấp khúc này có dạng OB₁B₂…B_k (nối từ O đến B₁, B₁ đến B₂, …, B_k-1 đến B_k) và phải thỏa mãn:

• 0 < x_B1 < x_B2 < … < x_Bk

• 0 < y_B1 > y_B2 < y_B3 > …

• Các điểm B_i (với i = 1, 2, …, k) phải thuộc tập điểm A₁, A₂, …, A_n.

Trong đó:

• x_B1, x_B2, …, x_Bk lần lượt là hoành độ của B₁, B₂, …, B_k;

• y_B1, y_B2, …, y_Bk lần lượt là tung độ của B₁, B₂, …, B_k;

Yêu cầu: Với tập điểm A₁, A₂, …, A_n. Hãy vẽ một đường gấp khúc (theo dạng răng cưa) thỏa mãn các điều kiện trên sao cho được nhiều điểm nhất (lưu ý rằng điểm được chọn phải là đỉnh của răng cưa).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n (n ≤ 10⁴);

• Trong n dòng sau, dòng thứ i chứa 2 số nguyên dương x_i và y_i tương ứng là hoành độ và tung tộ của điểm A_i (x_i, y_i ≤10⁴ với i = 1, 2, …, n).

Kết quả: Ghi một số nguyên duy nhất là số lượng điểm nhiều nhất thoả mãn điều kiện đề bài.

Ví dụ:

Subtask:

• Subtask 1: 60% số test n ≤ 20;

• Subtask 2: 40% số test còn lại không có ràng buộc gì thêm.