Trong một nhiệm vụ tối mật, người lính biệt kích CONTRA đã đột nhập thành công vào căn cứ chính của kẻ địch. Căn cứ này được xây dựng trên một khu vực dạng lưới kích thước . Có hành lang chạy dọc (đánh số từ đến từ trái sang phải) và hành lang chạy ngang (đánh số từ đến từ trên xuống dưới). Giao điểm của hành lang dọc thứ và hành lang ngang thứ được gọi là vị trí .
Để vận chuyển vũ khí và binh lính, kẻ địch đã lắp đặt hệ thống băng chuyền tự động. Mỗi băng chuyền có một điểm lên duy nhất. Lộ trình của mỗi hệ thống băng chuyền đều tạo thành một hình chữ nhật, di chuyển thuận chiều kim đồng hồ. Hệ thống thứ có lộ trình là hình chữ nhật với góc trái trên là vị trí và góc phải dưới là vị trí .
Tại thời điểm , CONTRA thâm nhập vào hệ thống ở vị trí , CONTRA cần di chuyển đến mục tiêu cuối cùng là lõi năng lượng trung tâm ở vị trí để phá đảo màn chơi. Lúc này, băng chuyền thứ đã hoạt động, điểm lên của nó (tương ứng với vị trí góc trái trên) đã di chuyển được một khoảng cách là . Bạn hãy giúp CONTRA xác định thời gian nhanh nhất để đến được lõi năng lượng.
Lưu ý rằng CONTRA có thể sử dụng nhiều băng chuyền. Khi anh ta nhảy khỏi một băng chuyền tại một vị trí ở thời điểm , anh ta có thể nhảy lên một băng chuyền khác cũng đi qua vị trí đó nếu băng chuyền đó tới nơi vào thời điểm trở đi.
Dữ liệu:
Dòng đầu tiên chứa số nguyên dương ().
Dòng thứ hai chứa số nguyên dương ().
Dòng thứ trong dòng tiếp theo, mỗi dòng chứa 5 số nguyên dương ().
Kết quả: In ra duy nhất một số nguyên là thời gian sớm nhất mà CONTRA có mặt tại mục tiêu. Dữ liệu đảm bảo luôn có cách di chuyển chỉ bằng băng chuyền để đến được mục tiêu cuối cùng.
Ví dụ:
Dữ liệu:
10 10 1 3 10 1
3
1 3 5 6 4
5 5 7 10 1
7 1 10 5 9
Kết quả:
50
Dữ liệu:
4 3 2 1 4 3
3
1 1 4 2 0
1 1 2 2 3
2 2 4 3 3
Kết quả:
6
Giải thích; Dưới đây là hình vẽ minh họa cho ví dụ . Trong đó, hình tam giác thể hiện điểm xuất phát của CONTRA, hình vuông thể hiện mục tiêu, các hệ thống băng chuyền được thể hiện bởi các mũi tên và vị trí mốc hiện tại của các băng chuyền được thể hiện bằng hình tròn.
