AT_arc116_f [ARC116F] Deque Game

[problemUrl]: https://atcoder.jp/contests/arc116/tasks/arc116_f $ K $ 個の数列が与えられます。 $ i $ 個目の数列 $ A_i $ の長さは $ N_i $ です。 これらを使って高橋君と青木君がゲームをします。 全ての数列が長さ $ 1 $ になるまで、高橋君と青木君が交互に以下の操作を行います。 - 長さが $ 2 $ 以上の数列を $ 1 $ つ選び、その最初の要素或いは最後の要素を削除する。 高橋君が先に操作を行います。最後に残る $ K $ 個の要素の総和を、高橋君は最大化したいと、青木君は最小化したいと考えています。 両者最適に行動するとき、最後に残る $ K $ 個の要素の総和を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ N_1 $ $ A_{1,\ 1} $ $ A_{1,\ 2} $ $ \cdots $ $ A_{1,\ N_1} $ $ N_2 $ $ A_{2,\ 1} $ $ A_{2,\ 2} $ $ \cdots $ $ A_{2,\ N_2} $ $ \vdots $ $ N_K $ $ A_{K,\ 1} $ $ A_{K,\ 2} $ $ \cdots $ $ A_{K,\ N_K} $

答えを出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \leq\ K\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ N_i $ - $ \sum_i\ N_i\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_{i,\ j}\ \leq\ 10^9 $ ### Sample Explanation 1 ゲームの進行の一例を示します。 - 高橋君が $ A_2 $ の最初の要素を削除する。現在の数列の状態は、 $ A_1\ =\ \left(1,\ 2,\ 3\right),\ A_2\ =\ \left(10\right) $ である。 - 青木君が $ A_1 $ の最後の要素を削除する。現在の数列の状態は、 $ A_1\ =\ \left(1,\ 2\right),\ A_2\ =\ \left(10\right) $ である。 - 高橋君が $ A_1 $ の最初の要素を削除する。現在の数列の状態は、 $ A_1\ =\ \left(2\right),\ A_2\ =\ \left(10\right) $ である。全ての数列の長さが $ 1 $ となった為、ゲームが終了する。 このとき、最後に残る $ K $ 個の要素の総和は $ 12 $ です。尚、このゲームの進行が両者にとって最適な行動であるとは限りません。