CF115E Linear Kingdom Races

你是一个赛车比赛的组织者，想在线性王国中安排一些比赛。 线性王国有 $n$ 条连续的从左到右的道路。道路从左到右依次编号为从 $1$ 到 $n$，因此道路按照升序排列。在这些道路上可能会有几场比赛，每一场比赛都将使用这些道路的某个连续的子序列。而且，如果某场比赛举行了，你将获得一定数额的金钱。没有比赛在时间上重叠，所以每一段道路可以在多个比赛中使用。 不幸的是，**所有道路**的状况都不佳，需要修理。每条路都有与之相关的维修费用，你需要支付这笔费用来修理道路。只有在某场比赛中需要使用的所有道路**都进行了修复**，才能进行比赛。你的任务是修复道路并使你的利润最大化。你的利润被定义为你从比赛中获得的总金额减去你花在修理道路上的钱。**请注意，您可以决定不修任何道路，并获得利润 $0$。** 输出你能获得的最大利润。

无

无

在第一个样例中，最优解是修复 $1, 2, 3, 7$。你将会在第 $1, 2, 4$ 三场比赛中获得 $15$ 的收益。道路修理费用是 $11$，因此你的利润是 $4$。