Cho một ma trận vuông (n × n) các ô có giá trị là 0, 1 hoặc -1. Tìm đường đi từ góc trái ô (1, 1) xuống gốc phải ô (n, n) với nguyên tắc chỉ được dịch chuyển sang phải hoặc xuống ô phía dưới và không được đi vào ô -1. Tìm đường đi tạo thành dãy nhị phân có giá trị lớn nhất.

Chú ý: Sử dụng kỹ thuật đệ quy quay lui và ngôn ngữ lập trình C++.

Input:

- Dòng đầu tiên gồm số nguyên dương n.

- n dòng tiếp theo, trên mỗi dòng ghi n số 0, 1 hoặc -1 các số này cách nhau một khoảng trắng.

Output: Một số nguyên là kết quả của bài toán.

Ví dụ: