Năm 1944, đặc nhiệm Mike nhận được lệnh từ Bộ Quốc phòng, yêu cầu lập tức đến một hòn đảo hoang trên Thái Bình Dương để giải cứu binh nhì Ryan đang bị quân địch bắt giữ. Ryan bị giam trong một mê cung có địa hình phức tạp, nhưng may mắn là Mike đã có bản đồ địa hình của mê cung. Mê cung có dạng hình chữ nhật, hướng Nam-Bắc được chia thành hàng, hướng Đông-Tây được chia thành cột, do đó toàn bộ mê cung được chia thành ô đơn vị. Vị trí của mỗi ô có thể được biểu diễn bằng một cặp số có thứ tự (số dòng, số cột). Giữa ô liền kề theo hướng Nam-Bắc hoặc Đông-Tây có thể thông nhau, hoặc có một cánh cửa bị khóa, hoặc là một bức tường không thể vượt qua. Trong mê cung có một số ô chứa chìa khóa, và tất cả các cửa được chia thành loại. Chìa khóa cùng loại sẽ mở được các cửa cùng loại, chìa khóa khác loại sẽ không mở được.
Binh nhì Ryan bị giam ở góc Đông Nam của mê cung, tức là ô , và đang trong tình trạng hôn mê. Mê cung chỉ có một lối vào ở góc Tây Bắc. Tức là, Mike có thể trực tiếp đi vào ô . Ngoài ra, thời gian để Mike di chuyển từ một ô sang ô liền kề là , thời gian nhặt chìa khóa tại ô đang đứng cũng như thời gian dùng chìa khóa mở cửa có thể bỏ qua.
Hãy thiết kế một thuật toán giúp Mike đến được ô của Ryan nhanh nhất để giải cứu anh ta.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên, lần lượt biểu thị giá trị của .
Dòng thứ hai là một số nguyên , biểu thị tổng số cửa và tường trong mê cung.
Dòng thứ , chứa số nguyên, lần lượt là :
Khi , nghĩa là giữa ô và ô có một cánh cửa loại .
Khi , nghĩa là giữa ô và ô có một bức tường không thể vượt qua.
Dòng thứ là một số nguyên , biểu thị tổng số chìa khóa trong mê cung.
Dòng thứ , chứa số nguyên, lần lượt là , biểu thị chìa khóa thứ nằm ở ô và chìa khóa thứ dùng để mở cửa loại .
Các số nguyên liền kề trên cùng một dòng được phân tách bằng một dấu cách.
Kết quả:
Xuất ra thời gian ngắn nhất để Mike giải cứu được binh nhì Ryan. Nếu bài toán vô nghiệm, xuất ra .
