#P11639. Line Game

Line Game

题目描述

你在玩一个音游。

这个音游可以抽象为一个长度为 m+1m+1 的线段。

这个音游有 n+mn+m 秒,在前 nn 秒中,第 ii 秒会在 11 处出现一个集合,这个集合可以用一个可重无序集 SiS_i 来表示,大小为 aia_i,每秒末尾这个集合的位置会增加 11

因为你不会玩,所以你有一个可爱的 bot,它在第 00 秒位于 11,之后每一秒你都需要选择一个值域区间 [l,r][l,r],若这个 bot 所处位置有一个非空的集合 QQ,那么 bot 会消去 QQ 中值域位于 [l,r][l,r] 的数,该操作代价为 rl+1r-l+1。除此之外,这个 bot 在每秒的末尾可以选择将自己的位置 +1+1

若有非空的集合到达 m+1m+1 处,那么你就失败了。请问在不失败的情况下你最少需要花费多少代价?

输入格式

第一行两个整数 n,mn,m

接下来 nn 行,每行第一个整数为 aia_i,接下来有 aia_i 个整数,表示集合 SiS_i

输出格式

一行一个整数,表示最小代价。

1 2
4 1 2 6 7
4

提示

[1,k][1,k] 为集合中元素的值域。

本题采用捆绑测试。

  • Subtask#1(10pts10\text{pts}):m=1m=1
  • Subtask#2(20pts20\text{pts}):n=1n=1
  • Subtask#3(15pts15\text{pts}):k=100k=100
  • Subtask#4(15pts15\text{pts}):m100m\le 100
  • Subtask#5(20pts20\text{pts}):m105m\le 10^5
  • Subtask#6(20pts20\text{pts}):无特殊限制。

对于 100%100\% 的数据,1n1001\le n\le 1001m1091\le m\le 10^91ai5×1041\le a_i\le 5\times 10^4,除 Subtusk#3 外 k=109k=10^9