题解

思路推导

对任意一个已经选定的消息集合，按 $b_i$ 从小到大阅读时，相邻差的总和恰好是集合中最大 $b_i$ 与最小 $b_i$ 的差。任何其他顺序的相邻差总和都不会更小。因此，只需考虑按 $b_i$ 排序后的阅读顺序。

把所有消息按 $b_i$ 非降序排列。固定一个左端点 $i$，再让右端点 $j$ 从 $i$ 向右移动。若最终选择的消息都位于区间 $[i,j]$，使用区间跨度 $b_j-b_i$ 后，剩余预算只能用于各消息的 $a_i$。在候选消息数量固定时，选择其中最小的若干个 $a_i$ 一定最优。

做法

枚举左端点 $i$。维护一个大根堆，依次把右端点 $j$ 对应的 $a_j$ 加入堆中，并维护堆中元素之和。

若当前元素之和加上 $b_j-b_i$ 超过 $l$，就不断删除堆中最大的 $a_i$，直到重新满足预算。此时堆里保留的是当前区间内尽可能多的较小 $a_i$，用堆的大小更新答案。

空集合始终合法，因此答案初值为 $0$。

正确性证明

首先，任意选定集合按 $b_i$ 非降序排列后，相邻差会望远镜相消为最大值减最小值；根据三角不等式，其他顺序不可能得到更小的相邻差总和。因此，最优方案一定可以按这种顺序阅读。

固定枚举到的 $i,j$。跨度费用取为 $b_j-b_i$。对于区间中的任意数量 $q$，使 $q$ 条消息的 $a_i$ 总和最小的方法就是选择区间内最小的 $q$ 个 $a_i$。大根堆每次在超出预算时删除当前最大的 $a_i$，所以调整完成后保留的条数正是这个区间在该跨度预算下能够保留的最大条数。即使堆中没有选择端点，实际所选集合的 $b_i$ 跨度只会更小，因此堆中方案仍然合法。

反过来，取任意一个最优非空集合，并令 $i,j$ 分别是它在排序后最左和最右的下标。当算法枚举到这对端点时，该集合中的全部消息都已经进入候选区间，其 $a_i$ 总和加 $b_j-b_i$ 不超过 $l$。堆的保留规则不会得到比这个集合更少的最大可行条数。因此算法得到的答案不少于最优答案；而算法记录的每个方案本身都合法，所以答案也不可能超过最优答案。两者相等。

复杂度分析

排序需要 $O(n\log n)$ 时间。枚举左右端点并维护堆需要 $O(n^2\log n)$ 时间，额外空间复杂度为 $O(n)$。