{"code":"robot","name":"Trò chơi với robot","description":"Trên lưới ô vuông gồm $𝑚$ dòng và $𝑛$ cột. Các dòng được đánh số từ 1 đến $𝑚$ từ trên xuống dưới, các cột được đánh số từ 1 đến $𝑛$ từ trái sang phải. Ô nằm giao giữa dòng $𝑖$ và cột $𝑗$ gọi là ô ($𝑖,𝑗$). Ban đầu, tại thời điểm 0, máy tính sẽ đặt $𝑘$ robot trên lưới, robot thứ $𝑟$ ($𝑟 =1,2, … , 𝑘$) được đặt ở ô ($𝑥_𝑟, 𝑦_𝑟$), các ô khác của lưới có thể đặt vật cản hoặc không. *Mỗi đơn vị thời gian, người chơi phải điều khiển di chuyển một số con robot trong $𝑘$ robot (có thể không điều khiển con nào).* Robot chỉ thực hiện di chuyển sang một trong các ô kề cạnh hoặc kề đỉnh với ô robot đang đứng và ô đó không có vật cản, việc di chuyển này mất đúng một đơn vị thời gian.\r\n\r\nNhiệm vụ của người chơi là di chuyển để $𝑘$ robot gặp nhau là sớm nhất, $𝑘$ robot được gọi là gặp nhau nếu chúng cùng đứng trong một ô. Để trò chơi thêm thú vị, nếu ô ($𝑖,𝑗$) có vật cản thì ở thời điểm $𝑑_{𝑖𝑗}$ vật cản sẽ biến mất và robot có thể đi vào ô ($𝑖,𝑗$) tính từ thời điểm $𝑑_{𝑖j}$\r\n\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa 3 số $𝑚, 𝑛, 𝑘$ ($𝑚 \\times 𝑛 \\leq 5000$);\r\n- Dòng thứ $𝑖$ trong $𝑚$ dòng tiếp theo chứa $𝑛$ số nguyên, số thứ $𝑗$ trong dòng nhận giá trị 0 mô tả ô ($𝑖,𝑗$) không có vật cản, hoặc -1 mô tả ô ($𝑖,𝑗$) có đặt robot, hoặc một số nguyên dương $𝑑_{𝑖𝑗}$ mô tả ô ($𝑖,𝑗$) có vật cản và $𝑑_{𝑖𝑗}$ là thời điểm vật cản ở ô đó biến mất ($𝑑_{𝑖𝑗} \\leq 10^9$).\r\n\r\n#### Output\r\n\r\n- Gồm một dòng chứa một số nguyên là thời điểm sớm nhất mà $𝑘$ robot gặp nhau, nếu không tồn tại cách di chuyển ghi -1.\r\n#### Scoring\r\n- Subtask $1$ ($25\\%$ số điểm): $𝑘 = 2$ và không có ô nào đặt vật cản;\r\n- Subtask $2$ ($25\\%$ số điểm): $𝑘 \\leq 5$ và không có ô nào đặt vật cản;\r\n- Subtask $3$ ($25\\%$ số điểm):$𝑘 = 2$;\r\n- Subtask $4$ ($25\\%$ số điểm): $𝑘 \\leq 5$.\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 4 2\r\n        -1 0 3 0\r\n        19 9 9 0\r\n        0 0 0 -1 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":600.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}