Bài 5. Đường đi tăng dần dài nhất

Mô tả

Cho ma trận số nguyên a[i][j]. Bạn được chọn một ô bắt đầu bất kỳ, sau đó di chuyển trên lưới.

Mỗi bước chỉ được đi:

• sang phải
• xuống dưới

Bạn chỉ được phép đi sang ô mới nếu giá trị ở ô mới lớn hơn giá trị ở ô hiện tại.

Hãy tìm độ dài lớn nhất của một đường đi như vậy. Độ dài đường đi được tính bằng số ô đi qua.

Input

• Dòng đầu ghi hai số nguyên n, m.
• n dòng tiếp theo, mỗi dòng gồm m số nguyên a[i][j].

Output

In ra độ dài lớn nhất của đường đi tăng dần.

Giới hạn

• 1 <= n, m <= 1000 nếu không có ghi chú khác.
• Dữ liệu bảo đảm phù hợp với kiểu 64-bit signed integer nếu bài yêu cầu tổng hoặc chi phí.

Subtask

• Subtask 1 (30%): 1 <= n, m <= 30.
• Subtask 2 (30%): các giá trị đôi một khác nhau.
• Subtask 3 (40%): 1 <= n, m <= 1000.

Ví dụ

Input

3 4
1 2 3 1
2 3 4 5
1 2 6 7

Output

6