从左到右依次考虑所有端点，进行决策。

为了便于处理线段重叠的情况，设 DP 状态 $f_{i,j}$ 为前 $i$ 个端点的所有决策中，覆盖点 $j$ 以左的部分最多有多长。

分类讨论这 $i$ 条线段，是否覆盖到了 $a_i$ 以右的点。

没有覆盖的话，$j=a_i$ 时的答案应该由 $j=a_i-l_i$ 的答案转移而来。

否则我们枚举右端点最靠右的线段 $k$，显然此时 $(k,i]$ 中的线段向右延伸一定不优于全部向左延伸。设 $(k,i)$ 中所有线段向左延伸的左端点为 $t$，那么 $j=a_k+l_k$ 时的答案应当由 $j=t$ 的答案转移而来。

此时我们处理完了 $j$ 恰好落在被覆盖的最靠右的点的情形。那么对此从左向右令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j-1})$，再从右向左地依次令 $f_{i,j}\leftarrow\max(f_{i,j},f_{i,j+1}-1)$。即可。这样做等效于将 $j$ 处的值改为 $\max(\max_{k\le j}f_{i,k},\max_{k>j}f_{i,k}-k+j)$，如果 $i$ 没有被覆盖，那么会取前者，否则会取后者（因为 $f_{i,j+1}-f_{i,j}\in[0,1]$）。

从前往后依次考虑每个段，不难发现，某个段内要么不表演，要么在不与之前的表演冲突的前提下，尽可能多地表演，即不需要迁就后面的段而让当前的段少表演，否则将后面段的表演移到前面段来，一定不劣。

既然如此，我们只需要 DP 求前 $i$ 段中最多唱多少首歌，设为 $f_i$；在唱最多歌的基础上，最早什么时候结束，设为 $g_i$。

暴力转移是 $O(n^2)$ 的。

考虑满足 $g_j\le l_i-t$ 的转移 $j\to i$，$i$ 段的决策一定是从 $l_i$ 开始唱歌，所以在只从最后一个这样的 $j$ 更新，一定不劣。

而对于 $g_j>l_i-t$ 的所有转移 $j\to i$，每个 $j$ 在整个过程中最多进行一次这样的转移，所以可以暴力做。

不难发现一个性质，如果某个方案中老鼠 $i,j$ 分别躲进了洞 $u,v$ 中，$x_i<x_j$ 而 $p_u>p_v$，显然调整为让 $i$ 躲进 $v$，$j$ 躲进 $u$，该方案一定不会变劣。因此，将老鼠按照起点所在的位置划分为几个连续段，这些连续段从左往右依次匹配从左往右的洞，一定不劣。

考虑朴素 DP，设 $f_{i,j}$ 表示前 $i$ 个洞匹配前 $j$ 个老鼠，老鼠需要走的总长度最小值。有

$$\displaylines{\begin{aligned} f_{i,j}&=\min_{k=j-c_i}^j\left\{f_{i-1,k}+\sum_{k<t\le j}|x_t-p_i|\right\}\\ &=\min_{k=j-c_i}^j\{f_{i-1,k}+s_{i,j}-s_{i,k}\}\\ &=s_{i,j}+\min_{k=j-c_i}^j\{f_{i-1,k}-s_{i,k}\} \end{aligned} }$$

其中 $s_{i,j}$ 表示 $\sum_{t\le j}|x_t-p_i|$，并且 $j$ 增大的过程中，$k$ 的合法取值区间单调右移，使用优先队列优化到 $O(nm)$。

令 $b_i=\gcd(a_1,a_2,\cdots,a_3)$， 不难发现 $b_{i+1}\mid b_i$。

于是我们设 $f_x$ 为将序列 $a$ 中所有 $x$ 的倍数重排得到序列 $t_1,t_2,\cdots,t_m$ 之后，$\sum_{i=1}^m\gcd(t_1,t_2,\cdots,t_i)$ 的最大值。

那么显然 $f$ 在 $x$ 处的值只会从它的所有倍数 $kx$ 处转移而来，并且 $f_{kx}$ 对应的最优的序列一定是 $f_x$ 对应的最优的序列的前缀。

转移方程为

$$\displaylines{f_x=\max_{kx\le\max\{a\}}\left\{f_{kx}+\sum_{i=1}^n[x\mid a_i\land kx\not\mid a_i]\right\} }$$

这样转移是 $O(n\log n)$ 的。

考虑到对于合数 $k=pq$（$p,q$ 不为 $1$），$f_{kx}\to f_{px}\to f_{qx}$ 的转移不比 $f_{kx}\to f_{x}$ 劣，所以实际上可以仅枚举所有质数 $k$ 进行转移。