Let us first simplify the problem and then make it progressively harder.

Case 1: \(K = 1\) and \(N_1\) is odd

Let us define a function \(f\) for an odd-length sequence:

\[ f\left(B\right) = \begin{cases} B_1 & \left(|B| = 1\right) \\ \min\left(B_{\frac{|B|+1}{2}}, \max\left(B_{\frac{|B|+1}{2}-1}, B_{\frac{|B|+1}{2}+1}\right)\right) & (|B| \geq 3) \end{cases} \]

Then, the answer is \(f\left(A_1\right)\). We can prove by induction that Takahashi can make the last value at least \(f(A_1)\) using the following strategy:

• if \(A_{1, \frac{|A_1|+1}{2}-1} \geq A_{1, \frac{|A_1|+1}{2}+1}\), delete the last element of \(A_1\);
• otherwise, delete the first element of \(A_1\).

On the other hand, we can again prove by induction that Aoki can make the last value at most \(f(A_1)\) using the following strategy:

• if \(|A_1| \geq 4\), delete the element in the direction opposite from the direction in which Takahashi deleted an element;
• if \(|A_1| = 2\), keep the element he prefers.

Case 2: \(N_i\) is odd \((i = 1, 2, \ldots K)\)

The answer is \(\sum_{i=1}^K f\left(A_i\right)\). We can prove by induction that Takahashi can make the sum of the last values remaining at least \(\sum_{i=1}^K f\left(A_i\right)\) using the following strategy:

• if this is the first operation of Takahashi or Aoki made an even-length sequence odd-length in his previous move, choose some sequence \(A_i\) of length at least \(2\) and use on it his strategy in Case 1; (We can prove that the length of \(A_i\) is odd as long as he follows this strategy.)
• otherwise, use Aoki’s strategy in Case 1 on the sequence \(A_i\) Aoki made his previous move on. (We can prove that the length of \(A_i\) is even as long as he follows this strategy.)

On the other hand, Aoki can make the sum of the last values remaining at most \(\sum_{i=1}^K f\left(A_i\right)\) using the following strategy:

• use his strategy in Case 1 on the sequence \(A_i\) Takahashi made his previous move on. (We can prove that the length of \(A_i\) is even as long as he follows this strategy.)

Case 3: the general case

Let us consider the case \(\sum_{i = 1}^K N_i - K\) is even here.

We can interpret the strategies above where \(N_i\) is odd \((i = 1, 2, \ldots K)\), as follows:

• Making an operation on an odd-length sequence \(A_i\) is not profitable. If \(|A_i| \geq 5\), the middle three elements will remain the same if the opponent deletes an element from the opposite direction; if \(|A_i| = 3\), it is more profitable for a player when the opponent first makes a move on \(A_i\) and then the player makes a move on it, than when the player first makes a move on \(A_i\) and then the opponent makes a move on it.

From this observation, we can generalize the strategies of the two players in Case 2, as follows:

• if all sequences have odd lengths, choose some sequence \(A_i\) of length at least \(2\) and delete the element at one of the two ends that is nearer to the less preferred element between \(A_{i, \frac{|A_i|+1}{2}-1} , A_{i, \frac{|A_i|+1}{2}+1}\);
• otherwise, compute the difference of \(f\left(A[1:|A_i|-1]\right)\) and \(f\left(A[2:|A_i|]\right)\) for each even-length sequence \(A_i\) and make the operation with the greatest profit.

Let us prove by induction that this strategy is optimal. If there is no even-length sequence, the proof is similar to the one in Case 2. Let us consider the case with some even-length sequences. If we make a move on an even-length sequence, from the inductive assumption, the next move by the opponent and the following moves will be made greedily, preferring the operation with the greatest profit, and it comes down to the case with only odd-length sequences. By considering this resulting situation, we can see that it is optimal to do the operation with the greatest profit in this turn. On the other hand, if we make a move on an odd-length sequence, the opponent can delete an element in this sequence from the opposite direction, resulting in a state where we have fewer elements in total, the same even-length sequences, and odd-length sequences that are not better than the ones we had. By considering the optimal strategy here obtained by inductive assumption, this progression is not better than the one that results if we make a move on an even-length sequence in the first place. Thus, we can see that the strategy above is optimal.

Therefore, by computing the difference of \(f\left(A[1:|A_i|-1]\right)\) and \(f\left(A[2:|A_i|]\right)\) and assuming that Takahashi and Aoki alternately choose the operation with the greatest profit greedily, the case can be reduced to Case 2, so we can solve the problem in \(O\left(N\log N\right)\) time.

The case \(\sum_{i = 1}^K N_i - K\) is odd is similar, but note that we have to change the definition of \(f\), since it will be Aoki, not Takahashi, who makes moves on odd-length sequences.