Imaichi Solution

行从上往下没有后效性，还是最优化问题，很容易想到 dp。

设 $f(i,j)$ 表示走到 $(i,j)$ 这一格的最多的摩拉，如果走不到就用 $-\infty$ 表示。

那么初状态是 $f(1,i)=min(a(1,i)+s,k)$，接着要考虑两种转移，一种是行改变的，另一种是行不改变的。

行改变的相对简单 $f(i,j)=\min(k,f(i-1,j)+a(i,j))$。

行不改变的就在这一行内进行转移。这时候发现原来的无后效性不存在了，于是需要发现性质，如果路径不绕圈就是往一个方向进行转移，可以直接

$f(i,j)\leftarrow \min(k,f(i,j+1)+a(i,j))$ $f(i,j)\leftarrow \min(k,f(i,j-1)+a(i,j))$

对于绕圈的，如果这个圈非正，可以贪心去除，那么它绕了一个正圈，一个绕圈路径可以分成很多连续段，也就是有一个连续段之和为正，也就是存在两个相邻的数，他们的和 $>0$。那么如果第一次碰到这两个格子的时候，碰到第一个格子的时候，肯定是有非负的摩拉，因为我们假设了这条路径，那么再经过另一个点，因为和为正，肯定也是非负的，然后还可以再次经过这两个点，得到形如 $x\rightarrow y\rightarrow x\rightarrow y\dots$ 的路径。“刷摩拉”，一直达到上界 $k$。那么可以直接把这两个格子中 $a$ 非负的格子的 $a$ 改成 $k$。（比如 $[-2,3]\rightarrow[-2,k],[0,1]\rightarrow[k,k]$）那么从 $(i,j_1)$ 到 $(i,j_2)$ 要么是直接走，要么就是需要到某个格子刷摩拉走一条左侧的折线或者右侧的折线，来刷摩拉。具体实现从左往右扫，从右往左扫，再从左往右扫即可。

但是这里没有考虑既往左又往右的情况。加上就是完备的，为什么？如果左侧有两个刷币点，那么能够前往最近的，就可以完成满币，不必前往下一个点。右侧同理，所以对于 $A\dots S \dots T \dots B$ 的样子， $S$ 是入口，$T$ 是出口，$A,B$ 是刷币点，可能走出来 $SABT,SAT$ 的路线，本质就是看 $A\rightarrow T,B \rightarrow T$ 哪个更优。每一次转折都一定要刷币，而关键的刷币点只有两个，所以最多转折两次，于是代码就是从左往右扫，从右往左扫，从左往右扫，从右往左扫。

统计答案就是得到 $\max f(n,i)$ 然后和 $0$ 比大小，得到答案。