P11639 Line Game

你在玩一个音游。 这个音游可以抽象为一个长度为 $m+1$ 的线段。 这个音游有 $n+m$ 秒，在前 $n$ 秒中，第 $i$ 秒会在 $1$ 处出现一个集合，这个集合可以用一个可重无序集 $S_i$ 来表示，大小为 $a_i$，每秒末尾这个集合的位置会增加 $1$。 因为你不会玩，所以你有一个可爱的 bot，它在第 $0$ 秒位于 $1$，之后每一秒你都需要选择一个值域区间 $[l,r]$，若这个 bot 所处位置有一个非空的集合 $Q$，那么 bot 会消去 $Q$ 中值域位于 $[l,r]$ 的数，该操作代价为 $r-l+1$。除此之外，这个 bot 在每秒的末尾可以选择将自己的位置 $+1$。 若有非空的集合到达 $m+1$ 处，那么你就失败了。请问在不失败的情况下你最少需要花费多少代价？

无

无

设 $[1,k]$ 为集合中元素的值域。 **本题采用捆绑测试。** - Subtask#1（$10\text{pts}$）：$m=1$； - Subtask#2（$20\text{pts}$）：$n=1$； - Subtask#3（$15\text{pts}$）：$k=100$； - Subtask#4（$15\text{pts}$）：$m\le 100$； - Subtask#5（$20\text{pts}$）：$m\le 10^5$； - Subtask#6（$20\text{pts}$）：无特殊限制。 对于 $100\%$ 的数据，$1\le n\le 100$，$1\le m\le 10^9$，$1\le a_i\le 5\times 10^4$，除 Subtusk#3 外 $k=10^9$。