Bạn đang chèo thuyền kayak qua một hệ thống hang động ngầm và đột nhiên nhận ra thủy triều đang lên và bạn bị mắc kẹt! May mắn thay, bạn có bản đồ của hệ thống hang động. Bạn bị kẹt cho đến khi thủy triều bắt đầu rút, vì vậy bạn sẽ ở đây một lúc. Trong thời gian chờ đợi, bạn muốn xác định con đường nhanh nhất để đến lối thoát ngay khi thủy triều bắt đầu rút.

Hệ thống hang động là một lưới kích thước \(N \times M\). Bản đồ của bạn gồm hai lưới số \(N \times M\): một lưới xác định chiều cao của trần hang ở mỗi ô, và một lưới xác định chiều cao của sàn hang ở mỗi ô. Sàn của hệ thống hang động có tính thẩm thấu, nghĩa là khi mực nước giảm xuống, sẽ không có nước đọng lại phía trên mực nước.

Bạn đang bị kẹt ở góc tây bắc của bản đồ. Mực nước hiện tại là \(H\) cm, và một khi nó bắt đầu giảm, nó sẽ giảm với tốc độ không đổi là 10 cm mỗi giây, xuống đến mức 0. Lối thoát nằm ở góc đông nam của bản đồ. Hiện tại nó đang bị ngập nước, nhưng nó sẽ trở nên khả dụng ngay khi thủy triều bắt đầu rút.

Tại bất kỳ thời điểm nào, bạn có thể di chuyển theo hướng bắc, nam, đông hoặc tây sang một ô liền kề với các ràng buộc sau:

• Mực nước, chiều cao sàn của ô hiện tại, và chiều cao sàn của ô liền kề đều phải thấp hơn ít nhất 50 cm so với chiều cao trần của ô liền kề. Lưu ý: điều này có nghĩa là bạn sẽ không bao giờ có thể đi vào một ô có khoảng cách giữa sàn và trần ít hơn 50 cm.
• Chiều cao sàn của ô liền kề cũng phải thấp hơn ít nhất 50 cm so với chiều cao trần của ô hiện tại.
• Bạn không bao giờ được di chuyển ra khỏi mép bản đồ.

Lưu ý rằng bạn có thể lên hoặc xuống bao nhiêu tùy thích với chiếc thuyền kayak của mình. (Bạn rất khỏe mạnh nhờ việc chèo thuyền này!) Ví dụ, bạn có thể đi từ một ô có sàn ở độ cao 10 cm sang một ô liền kề có sàn ở độ cao 9000 cm (giả sử các ràng buộc nêu trên được đáp ứng).

Các ràng buộc này được minh họa dưới đây:

• Trong hình đầu tiên, bạn không thể di chuyển sang phải vì mực nước thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm.
• Trong hình thứ hai, bạn không thể di chuyển sang phải vì chiều cao sàn của ô hiện tại thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm.
• Trong hình thứ ba, bạn không thể di chuyển sang phải vì chiều cao sàn của ô liền kề thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm. Bạn sẽ không bao giờ có thể vào ô đó từ bất kỳ hướng nào.
• Trong hình thứ tư, bạn không thể di chuyển sang phải vì chiều cao sàn của ô liền kề thấp hơn chiều cao trần của ô hiện tại ít hơn 50 cm.

Khi di chuyển từ ô này sang ô khác, nếu có ít nhất 20 cm nước còn lại trên ô hiện tại khi bạn bắt đầu di chuyển, bạn mất 1 giây để hoàn thành việc di chuyển (bạn có thể dùng thuyền kayak). Ngược lại, bạn mất 10 giây (bạn phải kéo thuyền). Lưu ý rằng thời gian chỉ phụ thuộc vào mực nước ở ô bạn rời đi, không phải ở ô bạn đi vào.

Sẽ mất một thời gian trước khi thủy triều bắt đầu rút, và vì vậy bạn có thể dành bao nhiêu thời gian tùy thích để di chuyển trước khi nước bắt đầu hạ xuống. Điều quan trọng là bạn cần bao nhiêu thời gian kể từ thời điểm nước bắt đầu hạ cho đến khi bạn đến được lối thoát. Bạn có thể tính toán thời gian này không?

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên duy nhất, \(T\): số lượng bộ thử nghiệm.
• Tiếp theo là \(T\) bộ thử nghiệm, mỗi bộ bắt đầu bằng một dòng chứa các số nguyên \(H\), \(N\) và \(M\), đại diện cho mực nước ban đầu (cm) và kích thước bản đồ. \(2N\) dòng tiếp theo chứa chiều cao trần và sàn như sau:
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên cách nhau bởi khoảng trắng. Số nguyên thứ \(j\) ở hàng thứ \(i\) đại diện cho \(C_{ij}\), chiều cao của trần nhà tính bằng cm tại vị trí lưới \((j, i)\), trong đó tọa độ \(i\) tăng dần về phía Nam, và tọa độ \(j\) tăng dần về phía Đông.
  • \(N\) dòng tiếp theo chứa \(M\) số nguyên cách nhau bởi khoảng trắng đại diện cho chiều cao của sàn, theo cùng định dạng.
• Tại vị trí bắt đầu, sẽ luôn có ít nhất 50 cm không khí giữa trần và mực nước ban đầu, và ít nhất 50 cm giữa trần và sàn.
• Vị trí lối thoát sẽ luôn có ít nhất 50 cm không khí giữa trần và sàn.
• Luôn có một đường thoát ra.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: t", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và t là thời gian, tính bằng giây, bắt đầu từ khi thủy triều bắt đầu rút, để bạn thoát ra khỏi hệ thống hang động. Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-6}\) so với câu trả lời đúng sẽ được chấp nhận.

Ghi chú

Có thể bạn có thể đi qua toàn bộ hệ thống hang động trước khi thủy triều bắt đầu rút. Trong trường hợp này, bạn có thể đợi ở lối thoát cho đến khi thủy triều bắt đầu rút, vì vậy câu trả lời trong trường hợp này phải là 0 (đây là trường hợp trong ví dụ thứ tư).

Ràng buộc

Phân nhóm

• Test set 1 (Visible Verdict):
  \(1 \le T \le 50\).
  \(1 \le N, M \le 10\).
  \(1 \le H \le 1000\).
  \(1 \le F_{xy} \le C_{xy} \le 1000\).

• Test set 2 (Hidden Verdict):
  \(1 \le T \le 50\).
  \(1 \le N, M \le 100\).
  \(1 \le H \le 10000\).
  \(1 \le F_{xy} \le C_{xy} \le 10000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
200 1 2
250 233
180 100
100 3 3
500 500 500
500 500 600
500 140 1000
10 10 10
10 10 490
10 10 10
100 3 3
500 100 500
100 100 500
500 500 500
10 10 10
10 10 10
10 10 10
100 2 2
1000 1000
1000 1000
100 900
900 100

Case #1: 11.7
Case #2: 3.0
Case #3: 18.0
Case #4: 0.0

Nguồn

Google Code Jam 2012, Vòng 1B, bài Tide Goes In, Tide Goes Out.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.