{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   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$"},{"iden":"input","content":"Input 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}$"},{"iden":"sample input 1","content":"2\n3 1 2 3\n2 1 10"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"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"},{"iden":"sample output 2","content":"12"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}