Ôi không! Sự cân bằng chính trị mỏng manh của thế giới cuối cùng đã sụp đổ, và mọi quốc gia đều đã tuyên chiến với nhau. Bạn đã cảnh báo bất cứ ai sẵn lòng lắng nghe rằng điều này sẽ xảy ra, nhưng họ có chú ý không? Ha! Bây giờ điều duy nhất bạn có thể hy vọng là sống sót càng lâu càng tốt.

May mắn thay (có thể coi là vậy), các trung tâm công nghiệp của mọi quốc gia đều đã bị ném bom nguyên tử, vì vậy phương thức tấn công duy nhất còn lại là tung ra hết đợt lính nghĩa vụ này đến đợt lính nghĩa vụ khác vào nhau. Điều này giới hạn mỗi quốc gia chỉ có thể tấn công các nước láng giềng trực tiếp của mình. Thế giới là một lưới \(R \times C\) với \(R\) hàng, được đánh số từ 1 ở cực Bắc đến \(R\) ở cực Nam, và \(C\) cột, được đánh số từ 1 ở cực Tây đến \(C\) ở cực Đông. Mỗi quốc gia chiếm một ô của lưới, có nghĩa là mỗi quốc gia có thể tiếp cận tối đa 4 quốc gia láng giềng liền kề.

Mọi quốc gia bắt đầu với một giá trị sức mạnh cụ thể mà ai cũng biết. Họ không có khái niệm về chiến lược nâng cao, vì vậy vào đầu mỗi ngày, họ sẽ chỉ đơn giản chọn người hàng xóm mạnh nhất của mình (ưu tiên quốc gia ở phía Bắc nhất, sau đó là phía Tây nhất nếu có kết quả hòa) và tấn công họ bằng một đội quân. Đội quân sẽ có sức mạnh bằng với sức mạnh hiện tại \(S\) của quốc gia đó; vào cuối ngày, nó sẽ làm giảm sức mạnh của người hàng xóm đó đi một lượng là \(S\). Một quốc gia có sức mạnh chạm mức 0 sẽ bị tiêu diệt. Lưu ý rằng tất cả các quốc gia tấn công cùng một lúc; sức mạnh của một đội quân là như nhau bất kể quốc gia đó có bị tấn công trong ngày hôm đó hay không.

Quốc gia của bạn nằm ở \((c, r)\), tại cột \(c\) và hàng \(r\). May mắn thay, quốc gia của bạn đang nghe theo lời khuyên của bạn, vì vậy bạn không cần phải tuân theo chiến lược điên rồ này. Bạn có thể chọn tấn công bất kỳ người hàng xóm nào của mình vào một ngày nhất định (hoặc không làm gì cả). Tuy nhiên, bạn không thể tấn công nhiều hàng xóm cùng lúc, hoặc tấn công với một đội quân có sức mạnh ít hơn sức mạnh tối đa hiện có.

Hãy xác định số ngày tối đa bạn có thể sống sót.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên, C, R, c, và r. R dòng tiếp theo, mỗi dòng chứa C số nguyên, cho biết sức mạnh bắt đầu \(S_{c_i,r_i}\) của quốc gia ở cột ci và hàng ri. Nó có thể bằng 0, cho biết quốc gia đó đã bị tiêu diệt. Sức mạnh bắt đầu của quốc gia bạn sẽ không phải là 0.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #A: " theo sau là:

• "B day(s)", trong đó B là số ngày nhiều nhất bạn có thể hy vọng sống sót.
• "forever", nếu bạn có thể sống lâu hơn tất cả những người hàng xóm của mình.

Ràng buộc

• \(1 \le T \le 100\)
• \(1 \le c \le C\)
• \(1 \le r \le R\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le C \le 5\)
• \(1 \le R \le 5\)
• \(0 \le S_{ci,ri} \le 10\)
• Large dataset (Test set 2 - Hidden):
• \(1 \le C \le 50\)
• \(1 \le R \le 50\)
• \(0 \le S_{ci,ri} \le 1000\)

Đ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ụ

2
3 3 2 2
2 3 2
1 7 1
2 1 2
4 3 2 1
1 2 2 0
10 8 5 10
10 2 9 10

Case #1: forever
Case #2: 3 day(s)

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Apocalypse Soon.

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