背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

小 c 和 小 z 学习了博弈论的落后知识，他们打算玩 Nim 游戏以提高博弈论的先进性。

题目描述

众所周知，Nim 游戏本质上就是幼儿园小朋友的玩石子的小游戏，于是他们找到了许多石子，并将其分为 $n$ 堆并排成一排，从左到右第 $i$ 堆有 $a_i$ 个石子。

而说到石子，当然就不能不提到大名鼎鼎的动态规划入门经典题目《石子合并》。

所以在最初的规则中由两人轮流进行操作，每次操作者可以选择合并两堆相邻的石子，如此操作直到剩下一堆石子。小 c 希望这堆石子尽量少，小 z 则希望这堆石子尽量多。

小 c 和小 z 希望知道在二人绝顶聪明的情况下最终这堆石子的大小是多少——才怪，显然按照上述规则最终一堆石子的大小一定是 $\sum_{i=1}^{n} a_i$，与二人的操作无关。

于是他们决定增添一些新的规则，新规则如下：仍由两人轮流操作，每次操作者可以选择合并两堆相邻的石子，或者扔掉目前最靠左的一堆石子，或者扔掉目前最靠右的一堆石子（不能不操作），直到剩下一堆石子。小 c 希望这堆石子尽量少，小 z 则希望这堆石子尽量多。

仍然假设二人聪明绝顶（虽然这在实际上并不可能（至少对小 c 不可能）），问最后这堆石子的大小是多少？

注意，为了公平起见，每次游戏开始时他们会决定谁先手，而不是固定的由小 c 先手或者小 z 先手。

输入格式

从标准输入读入数据。

第一行两个整数 $n, k$；

其中 $k \in \{0, 1\}$。$k = 0$ 表示小 c 先手，$k = 1$ 表示小 z 先手；

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出到标准输出。

输出一行一个整数表示答案。

2 0
1 2

1

提示

样例 1 解释

本局小 c 先手，显然他会选择扔掉最靠右的一堆。

子任务

::cute-table{tuack}

对于 100% 数据，$1 \leq n \leq 10^5$，$0 \leq k \leq 1$，$a_i > 0$，$\sum_{i=1}^{n} a_n \leq 10^9$。