Music Game Bot Optimization

You are playing a rhythm game which can be modeled as a line segment of length \(m+1\). The game lasts for \(n+m\) seconds. In the first \(n\) seconds, at the \(i\)-th second a collection \(S_i\) appears at position 1. This collection is a multiset of numbers and has size \(a_i\). At the end of every second, each collection (if not completely erased) moves one unit to the right.

You control a cute bot that initially is at position 1 (at time 0). In each subsequent second, the bot must choose a value range interval \([l, r]\). If the current set \(Q\) at the bot's position is nonempty, the bot will delete from \(Q\) all numbers whose value lies in \([l,r]\). The cost of this deletion operation is \(r-l+1\). In addition, at the end of each second, the bot may move forward, i.e. increase its position by 1.

If any nonempty collection reaches position \(m+1\) (i.e. moves out of the playable range), you lose. Otherwise, you want to clear all collections completely at minimum total cost. Each collection \(S_i\) (which contains \(a_i\) numbers) must have all its numbers deleted before it moves from position \(m\) to \(m+1\) (you have exactly \(m\) deletion opportunities for each collection).

The twist is: you know the exact values in every collection. In the \(i\)-th second, after reading \(a_i\), you are given \(a_i\) integers representing the numbers in \(S_i\). For each collection, you are allowed to perform at most \(m\) deletion operations. In each deletion operation you choose an interval \([l, r]\) (with cost \(r-l+1\)) and all numbers in \(S_i\) whose values lie in \([l,r]\) will be removed. Note that if several copies of the same number exist, one deletion operation covering that number removes all of them.

Your task is to compute the minimum total cost to clear all collections without failing (i.e. without any collection reaching position \(m+1\)).

Hint:

For a single collection with sorted numbers \(x_1, x_2, \dots, x_k\), if you use just one deletion operation it would cost \(x_k - x_1 + 1\). However, if you are allowed to use more operations (up to \(m\) operations), you can split the interval into several parts. In fact, notice that if the gaps between consecutive numbers are large, you can save cost by not covering these gaps. Formally, if you compute the gaps \(g_i = x_{i+1} - x_i - 1\), then with up to \(m-1\) splits you can subtract the sum of the \(m-1\) largest gaps from \(x_k - x_1 + 1\). Of course, the cost cannot be less than \(1\) for a nonempty set.

The overall answer is the sum of the minimum deletion costs for all collections.

inputFormat

The first line contains two integers \(n\) and \(m\) (where \(1 \leq n, m \leq 10^5\)).

Then \(n\) groups follow. For the \(i\)-th group, the first line contains an integer \(a_i\) (\(1 \leq a_i \leq 10^5\)), the size of the multiset \(S_i\). The second line contains \(a_i\) space-separated integers representing the elements of \(S_i\). The values can be any integers (their absolute values do not exceed \(10^9\)).

outputFormat

Output a single integer: the minimum total cost required to clear all the collections without any nonempty collection reaching position \(m+1\).

sample

1 1
3
1 2 3

3