Joisino 要去打 final。这场比赛中，有 $N$ 道题，编号从 $1$ 到 $N$ 。Joisino 做第 $i$ 道题花费的时间为 $T_i$ 。

这场比赛中，选手的做题方式是选择自己想做的题来做，并且一定能做出来。最后，选手的得分将以如下方式计算：

$$得分 = \text{满足条件的二元组 $(l, r)$ 的个数} - \text{解决选了的题所花费的时间} $$

其中，二元组 $(l, r)$ 需要满足的条件是：对于所有满足 $l \le i \le r$ 的 $i$ ，第 $i$ 题都做了。另外， $l$ 和 $r$ 还需满足 $1 \le l \le r \le N$ 。

注意，选手可以选择对所有题弃疗，这样他将爆零。

主办方为参赛者提供了 $M$ 种饮料，从 $1$ 标号至 $M$ 。如果 Joisino 喝了第 $i$ 种饮料，他做第 $P_i$ 题时会兴奋，做第 $P_i$ 题的时间将从 $T_{P_i}$ 变成 $X_i$ ，注意 $X_i$ 不一定比 $T_{P_i}$ 小；做其它题的时间不受影响。

一位参赛者能且仅能带一种饮料进入考场。Joisino 想知道如果他喝下了每种饮料，他的最大得分。

感谢@OrangeLee 提供的翻译