{"problem":{"name":"Farm King X","description":{"content":"Mr.X has a large farm, which consists of $N \\times N$ squares.   We call the square at the $r$\\-th row from the top and at the $c$\\-th column from the left as the area $(r, c)$ $(0≤r, c＜N)$. $M$ veget","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"rcl_contest_2021_long_a"},"statements":[{"statement_type":"Markdown","content":"Mr.X has a large farm, which consists of $N \\times N$ squares.  \nWe call the square at the $r$\\-th row from the top and at the $c$\\-th column from the left as the area $(r, c)$ $(0≤r, c＜N)$.\n$M$ vegetables will grow and die on the farm in the coming $T$ days.  \nThe $i$\\-th vegetable is represented by five integers $R_{i},C_{i},S_{i},E_{i},$ and $V_{i}$.  \nThey mean that a vegetable with the value $V_{i}$ will appear in the area $(R_{i},C_{i})$ on the $S_{i}$\\-th day, and disappear at the end of the $E_{i}$\\-th day.\nX harvests these vegetables with harvest machines.  \nAt first, he doesn't have any harvest machines and has $1$ unit of money.\nOn each of the $T$ days, X makes one of the following actions.\n\n*   **Purchase**\n\n*   X gets a new harvest machine and puts it in one of the areas that doesn't have another harvest machine.\n*   When X has $j$ harvest machines, purchase costs $(j+1)^3$ units of money.\n    *   For example, the first purchase costs $1$ unit of money. The second purchase costs $8$ units of money, and so on.\n*   X can't purchase a machine if he doesn't have enough money.\n\n*   **Move**\n    *   X chooses a harvest machine and moves it to one of the areas where no harvest machine is located.\n*   **Pass**\n    *   X does nothing.\n\nAfter the $t$\\-th $(0≤t＜T)$ action, the following things happen in order.  \n\n*   For all i where $S_{i} = t$, vegetable $i$ appears in the area $(R_{i},C_{i})$.\n*   Vegetables in the areas that have a harvest machine are harvested.\n    *   For each of such vegetables, let $v$ be its value, and $k$ be the size of the 4-connected component of the areas having a harvest machine that contains the vegetable's position.\n        *   4-connected component is the group of areas that are connected to each other through vertically or horizontally adjacent areas.\n    *   X earns $v \\times k$ units of money.\n    *   This vegetable disappears.\n*   For all i where $E_{i} = t$, vegetable $i$ disappears from the farm if it's not yet harvested.\n\nYour goal is to make as much money as possible he has after the $T-1$\\-th day by determining actions X will take.\n\n### Scoring\n\nThe score of a test case is the amount of money X has after the $T-1$\\-th day.  \nThe score of a submission is the total score for each test case.\n\n*   Provisional tests consist of 50 test cases. If you get a result other than `AC` for one or more test cases, the score of the submission will be zero.\n*   System tests consist of 1000 test cases. If you get a result other than `AC` for some test cases, only the score for those test cases will be zero.  \n    Since there will be some variance in the execution time, submissions that are very close to the time limit may result in `TLE` in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time. We will publish [seeds.txt](https://img.atcoder.jp/rcl-contest-2021-long/seeds.zip) (md5=75031719692fe939fb105e7af16e31c8) after the contest is over.\n\n## Input\n\nInput is given from standard input in the following format.  \nThe first line consists of the three integers $N,M,T$ separated by a space. Each of the next $M$ lines consists of the five integers separated by a space.\n\n$N$ $M$ $T$\n$R_{0}$ $C_{0}$ $S_{0}$ $E_{0}$ $V_{0}$\n\\(\\\\vdots\\)\n$R_{i}$ $C_{i}$ $S_{i}$ $E_{i}$ $V_{i}$\n\\(\\\\vdots\\)\n$R_{M-1}$ $C_{M-1}$ $S_{M-1}$ $E_{M-1}$ $V_{M-1}$\n\n*   $N$ is an integer that represents the size of the farm and satisfies $N=16$.\n*   $M$ is an integer that represents the number of the vegetables and satisfies $M=5000$.\n*   $T$ is an integer that represents the number of days and satisfies $T=1000$.\n*   $R_{i}$ and $C_{i}$ are integers that represent the area in which $i$\\-th vegetable appears, and satisfy $0≤R_{i}＜N$, $0≤C_{i}＜N$.\n*   $S_{i}$ is an integer that represents the day which $i$\\-th vegetable appears on, and satisfies $S_{i}≤S_{i+1},0≤S_{i}＜T$.\n*   $E_{i}$ is an integer that represents the day which $i$\\-th vegetable disappears on, and satisfies $S_{i}≤E_{i}＜T$.\n*   $V_{i}$ is an integer that represents the value of the $i$\\-th vegetable. See the \"test case generation\" section below about the details.\n*   If $(R_i, C_i)=(R_j, C_j) (i＜j) $ , then $E_i＜S_j$. That is, the lifetimes of the vegetables that appear in the same area don't overlap.\n\n## Tools\n\nWe provide the tools for contestants. It contains test case generator, output verifier, sample input data, solution visualizer, and sample solutions (C++, Python).\n[contestant tools(zip)](https://img.atcoder.jp/rcl-contest-2021-long/9ee3ca1da522fff7e369dd7f470f1e7a.zip)\n\n## Visualizer\n\n*   This visualizer is tested on the latest desktop version of [Google Chrome](https://www.google.com/chrome/) and [Mozilla Firefox](https://www.mozilla.org/firefox/new/). We don't guarantee that it works on every browser.\n*   The score calculated on this visualizer is not the actual score of the contest. Submit your solution on the AtCoder contest page to enter the contest.\n*   Use this visualizer at your own risk.\n\nThis visualizer is also contained in the contestant tools.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"rcl_contest_2021_long_a","tags":[],"sample_group":[["9 4 10\n3 3 1 5 35\n4 4 4 6 22\n8 8 7 9 20\n2 3 8 9 10\n\nNotice: This input is for the explanation purpose and doesn't conform to the constraint.","3 3\n-1\n2 3\n3 4\n2 3 4 4\n3 3 7 8\n4 4 7 7\n3 4 8 7\n8 8\n-1\n\nOutput\n\nExplanation\n\nHarvest Machines Placement\n\nChange of Money\n\n3 3\n\nX purchases a harvest machine with $1$ unit of money, and places it to the area $(3,3)$.\n\n\\---------\n---------\n---------\n---o-----\n---------\n---------\n---------\n---------\n---------\n\n1 -> 0\n\n\\-1\n\nX does nothing.  \nA vegetable appears in the area $(3,3)$ and is harvested.  \nX earns $35 \\times 1 = 35$ units of money.\n\n\\---------\n---------\n---------\n---o-----\n---------\n---------\n---------\n---------\n---------\n\n0 -> 35\n\n2 3\n\nX purchases a harvest machine with $8$ units of money, and places it to the area $(2,3)$.\n\n\\---------\n---------\n---o-----\n---o-----\n---------\n---------\n---------\n---------\n---------\n\n35 -> 27\n\n3 4\n\nX purchases a harvest machine with $27$ units of money, and places it to the area $(3,4)$.\n\n\\---------\n---------\n---o-----\n---oo----\n---------\n---------\n---------\n---------\n---------\n\n27 -> 0\n\n2 3 4 4\n\nX moves a harvest machine located on $(2,3)$ to the area $(4,4)$.  \nAfter that, a vegetable appears in the area $(4,4)$ and is harvested.  \nX earns $22 \\times 3 = 66$ units of money.\n\n\\---------\n---------\n---------\n---oo----\n----o----\n---------\n---------\n---------\n---------\n\n0 -> 66\n\n3 3 7 8\n\nX moves a harvest machine located on $(3,3)$ to the area $(7,8)$.\n\n\\---------\n---------\n---------\n----o----\n----o----\n---------\n---------\n--------o\n---------\n\n66 -> 66\n\n4 4 7 7\n\nX moves a harvest machine located on $(4,4)$ to the area $(7,7)$.\n\n\\---------\n---------\n---------\n----o----\n---------\n---------\n---------\n-------oo\n---------\n\n66 -> 66\n\n3 4 8 7\n\nX moves a harvest machine located on $(3,4)$ to the area $(8,7)$.\n\n\\---------\n---------\n---------\n---------\n---------\n---------\n---------\n-------oo\n-------o-\n\n66 -> 66\n\n8 8\n\nX purchases a harvest machine with $64$ units of money, and places it to the area $(8,8)$.  \nAfter that, a vegetable in the area $(8,8)$ is harvested.  \nX earns $20 \\times 4 = 80$ units of money.\n\n\\---------\n---------\n---------\n---------\n---------\n---------\n---------\n-------oo\n-------oo\n\n66 -> 82\n\n\\-1\n\nX does nothing. A vegetable in the area $(2,3)$ disappears.\n\n\\---------\n---------\n---------\n---------\n---------\n---------\n---------\n-------oo\n-------oo\n\n82 -> 82\n\nThe score obtained from this output is $82$."]],"created_at":"2026-03-03 11:01:14"}}