{"code":"robotontheboard","name":"Robot on the Board","description":"Robot nằm trên một tấm bảng hình chữ nhật có ca rô kích thước $n * m$ ($n$ hàng, $m$ cột). Các hàng trong bảng được đánh số từ $1$ đến $n$ từ trên xuống dưới, và các cột - từ $1$ đến $m$ từ trái sang phải:\r\n\r\n</p>\r\n\r\nRobot có thể đứng ở một ô và di chuyển từ ô hiện tại sang **một** trong bốn ô liền kề.\r\n\r\n</p>\r\n\r\n\r\n- Mỗi ô trên bảng được gán một số nguyên.\r\n\r\n- Mỗi ô có một trong các kí hiệu '**`L`**', '**`R`**', '**`D`**' hoặc '**`U`**' được viết trên đó, cho biết hướng mà robot sẽ di chuyển khi ở trong ô đó - **trái**, **phải**, **xuống** hoặc **lên**, tương ứng.\r\n\r\n</p>\r\n\r\nRobot có thể bắt đầu di chuyển ở **bất kì** ô nào. Sau đó Robot di chuyển đến hình vuông liền kề theo hướng được chỉ ra ở hình vuông hiện tại và di chuyển 1 lần. \r\n\r\n</p>\r\n\r\n\r\n - Nếu robot di chuyển vào một ô chứa số nguyên nó sẽ nhận giá trị đó và mỗi ô chỉ được nhận  **duy nhất 1 lần** (Sau khi nhận giá trị từ ô đó thì giá trị của ô đó **bằng `0`**).\r\n\r\n - Nếu robot di chuyển ra ngoài mép bảng hình chữ nhật, robot sẽ bị rơi và vỡ.\r\n\r\n - Nếu robot xuất hiện trong ô mà nó đã truy cập trước đó, nó sẽ bị hỏng (dừng lại và không di chuyển nữa). \r\n\r\n</p>\r\n\r\nRobot có thể chọn bất kỳ ô nào làm ô bắt đầu. Mục tiêu của nó là nhận được **giá trị lớn nhất** trước khi ngắt hoặc dừng.\r\n\r\n</p>\r\n\r\nXác định xem robot sẽ bắt đầu chuyển động từ ô vuông nào để nhận được **giá trị lớn nhất** có thể.\r\n\r\n</p>\r\n\r\n### **Input Specification**\r\n---\r\n\r\n - Dòng đầu tiên chứa 2 số nguyên dương n và m. $(1 \\leq n \\leq 2000; 1 \\leq m \\leq 2000)$ - thể hiện chiều cao và chiều rộng của bảng.\r\n\r\n - Theo sau bởi $n$ dòng, dòng thứ $i$ gồm $m$ số nguyên $a_{i,1}, a_{i,2}, a_{i,3},...,a_{i,m}.$ $(0 \\leq a_{i,j} \\leq 10^9)$\r\n\r\n - Tiếp theo là $n$ dòng, dòng thứ $i$ là một xâu gồm $m$ kí tự thuộc các kí tự  '**`L`**', '**`R`**', '**`D`**' và '**`U`**'.\r\n\r\n\r\n</p>\r\n\r\n### **Output Specification**\r\n---\r\n - Xuất ra ba số nguyên $r, c$ và $d$ $($$1 ≤ r ≤ n$; $1 ≤ c ≤ m$; $d ≥ 0$$)$, biểu thị rằng robot sẽ bắt đầu di chuyển từ ô $(r, c)$ để nhận được **giá trị `d` lớn nhất**. \r\n - Nếu có nhiều đáp án, hãy xuất ra đáp án có **r bé nhất, nếu nhiều đáp án có $r$ bằng nhau thì xuất ra đáp án có $c$ bé nhất** \r\n\r\n</p>\r\n\r\n### **Scoring**\r\n---\r\n\r\n| **Subtask** | **Desciption** | **Account for** | \r\n| :----- | :---------- | :-------------- | \r\n| **1**      | **$n, m \\leq 50$**          | **$50\\%$**             | \r\n| **2**      | **$n, m \\leq 2 * 10^3$**        | **$50\\%$**               | \r\n\r\n### **Example**\r\n---\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 6\r\n        6 1 6 1 4 4\r\n        4 0 2 6 1 5\r\n        1 7 4 6 3 9\r\n        5 7 8 3 5 8\r\n        RURULD\r\n        LDULDD\r\n        RUURUL\r\n        RLULUD\r\n\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4 4 24\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Robot xuất phát từ ô $(4, 4)$ với lộ trình: $(4, 4)$ -> $(4, 3)$ -> $(3, 3)$ -> $(2, 3)$ -> $(1, 3)$ -> $(1, 4)$ và có giá trị thu được lần lượt là: $3 + 8 + 4 + 2 + 6 + 1 = 24$ và đó cũng là giá trị lớn nhất  .","points":1800.0,"partial":false,"time_limit":1.5,"memory_limit":262144,"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}}