建系，横坐标为时间，纵坐标为速度，将一只鹅用一条从 $(T_i,A_i)$ 到 $(T_i+L,A_i)$ 的水平直线表示出来。

我们设 $i$ 时刻速度最快的且当前还没有吃到东西的鹅的速度为 $U_i$，那么将 $U_i$ 在折线图上画出来。我们称一条线段为被覆盖的当且仅当其完全被 $U$ 的折线下面的部分（包含折线本身）覆盖。如图，其中鹅 $1,3$ 是被覆盖的，$2,4,5$ 是未被覆盖的。

显然我们只要确定了 $U$，就可以确定其答案。一种喂食鹅的方案至少对应一个 $U$。只要枚举所有可能的 $U$，就可以求出最优答案。但是当前 $U$ 的结构很难 DP，这是因为一条线段只要有一部分没有被 $U$ 覆盖，那么就会产生贡献，但是一条线段可能被 $U$ 经过很多次，所以我们不清楚当前是否是第一次经过某条线段。

所以，我们继续寻找性质。从左到右观察折线 $U$ 的走向，一条显然的性质是：当折线上升时，一定是上升到某个鹅的 $\color{red}{起点}$。

原因显然，我们上升折线的目的是：想要完全覆盖某个鹅。而如果我们没有从一个鹅的起点开始覆盖，那显然不会有用。如果你上去完全没有碰到任何一个鹅，那么你上去也没有用。所以当折线上升时一定是上升到某个鹅的起点。

同理，当折线下降时，一定是从某个鹅的 $\color{red}{终点}$ 开始下降。这也是显然的，不然不能完全覆盖一个鹅。

同时我们观察到一个性质，下面这个 $U$ 的走向是不优的：

更加强大的发现：$U$ 折线覆盖的任何一个鹅，其不被覆盖的部分一定是一个连续的区间。

观察上面这张图，我们将 $U$ 上升后，长度还没有到达 $L$（因为下面这个鹅还没结束，所以上升后保持的长度没有达到 $L$），就下降下来了。注意到每个鹅的长度是一样的，都是 $L$。在这里，我们上升后都没有保持长度为 $L$ 就下来了，显然是不可能成功将任何一只鹅完全覆盖的。

所以说这种中间凸起来的可以直接压平。当然，如果我们根据「只有线段出现时才能上升，只有线段消失时才能下降」的规则去维护 $U$，这种结构是不可能出现的。综上，$U$ 折线覆盖的任何一个鹅，其不被覆盖的部分一定是一个连续的区间：

（上面这种是可以的。）

那么我们发现，我们在什么时候计入一个鹅的代价时是不会算重的呢：

• 对于所有在当前时刻 $i$ 开始出现，且速度大于 $U_i$ 的鹅计入贡献。
• 下降折线时，切过的线段。

显然，因为

这种结构是不可能出现的（按照我们的 $U$ 的计算方法的话），所以说一条线段只能被计入一次。

我们实时维护 $s_j$ 表示所有起点 $< i$ 终点 $> i$ 且速度大于 $j$ 的鹅。那么从 $u$ 下降到 $v$ 的贡献就是 $s_v-s_u$（还要加上从当前时刻出现的鹅，这是后话）。

设 $f_j$ 表示当前 $U_i=j$ 的答案。我们有三类转移：

• 若 $j$ 不变，那么加上 $j$ 以上的新出现的线段的贡献即可。
• 若 $j$ 变大，则必定是变成新出现的线段的 $y$，这种情况总共出现 $O(n)$ 次。
• 若 $j$ 变小，设 $j$ 转移到 $j'$，则转移时贡献要加上 $x$ 跨过当前 $i$ 的且 $y \in [j', j)$ 的线段。

我们要做的形如：

• $f$ 的区间加、查询区间 $\max$
• $s$ 的区间加、查询单点
• 给定 $l, r, w$，
  $\forall j \in [l, r],\; f_j \leftarrow \max(f_j,\; s_j + w)$。

可以用线段树维护这些操作，时间复杂度 $O(n \log n)$。