#1344. DMAZE

Cho bảng gồm dòng và cột. Mỗi ô được đánh số từ đến . Ô giao bởi hàng và cột được đánh số .

Có tất cả ô bị cấm, ô đầu tiên là ô đánh số , các ô tiếp theo được tính theo công thức .

Từ một ô đánh số bạn được di chuyển:

• Xuống dưới: sang ô ;
• Sang phải: sang ô ;
• Theo đường chéo xuống dưới, sang phải: sang ô ;

Yêu cầu: Chọn một ô tùy ý, tìm đường đi dài nhất qua ít nhất ô sao cho không đi qua ô cấm, không đi ra ngoài bảng.

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên ;
• Dòng thứ hai chứa năm số nguyên .

Dữ liệu ra:

• Dòng đầu ghi độ dài đường đi dài nhất tìm được hoặc nếu không tồn tại đường đi thỏa mãn;
• Nếu dòng đầu khác thì dòng thứ hai mô tả đường đi từ ô xuất phát đến ô kết thúc.

Ví dụ:

Dữ liệu vào:

5 6 7
13 1 8 5 29

Dữ liệu ra:

8
6 11 16 17 18 24 25 30

Giải thích:

• Các ô cấm: và ;
• Các đường đi thỏa mãn:
  • ;
  • .

Chú ý:

• Nếu trả lời đúng độ dài đường đi mà không in đường đi thì được số điểm của test.