{"problem":{"name":"Deque Game","description":{"content":"We have $K$ sequences. The $i$\\-th sequence $A_i$ has the length of $N_i$. Takahashi and Aoki will play a game using these. They will alternately do the following operation until the length of every s","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc116_f"},"statements":[{"statement_type":"Markdown","content":"We have $K$ sequences. The $i$\\-th sequence $A_i$ has the length of $N_i$.\nTakahashi and Aoki will play a game using these. They will alternately do the following operation until the length of every sequence becomes $1$:\n\n*   Choose a sequence of length at least $2$, and delete its first or last element.\n\nTakahashi goes first. Takahashi wants to maximize the sum of the $K$ elements remaining in the end, while Aoki wants to minimize it.\nFind the sum of the $K$ elements remaining in the end when both players play optimally.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq K \\leq 2 \\times 10^5$\n*   $1 \\leq N_i$\n*   $\\sum_i N_i \\leq 2 \\times 10^5$\n*   $1 \\leq A_{i, j} \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$K$\n$N_1$ $A_{1, 1}$ $A_{1, 2}$ $\\cdots$ $A_{1, N_1}$\n$N_2$ $A_{2, 1}$ $A_{2, 2}$ $\\cdots$ $A_{2, N_2}$\n$\\vdots$\n$N_K$ $A_{K, 1}$ $A_{K, 2}$ $\\cdots$ $A_{K, N_K}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc116_f","tags":[],"sample_group":[["2\n3 1 2 3\n2 1 10","12\n\nHere is one possible progression of the game:\n\n*   Takahashi deletes the first element of $A_2$. Now we have $A_1 = \\left(1, 2, 3\\right), A_2 = \\left(10\\right)$.\n*   Aoki deletes the last element of $A_1$. Now we have $A_1 = \\left(1, 2\\right), A_2 = \\left(10\\right)$.\n*   Takahashi deletes the first element of $A_1$. Now we have $A_1 = \\left(2\\right), A_2 = \\left(10\\right)$. The length of every sequence has become $1$, so the game ends.\n\nIn this case, the sum of the $K$ elements remaining in the end is $12$. Note that the players may have made suboptimal moves here."],["8\n1 2\n2 1 2\n3 1 2 1\n4 1 1 1 2\n5 1 1 2 2 1\n6 2 2 2 2 1 1\n7 1 2 1 1 2 2 2\n8 2 2 2 1 1 1 1 2","12"]],"created_at":"2026-03-03 11:01:14"}}