최대공약수 합의 최댓값

Bit의 옷장에는 프로그래밍 대회 T셔츠가 많이 있다. 셔츠는 높이가 서로 다른 더미로 여러 선반에 쌓여 있다.

Bit은 어릴 때부터 최대공약수가 들어가는 게임을 좋아했다. 그래서 각 선반에 있는 더미의 셔츠 수에 대해 최대공약수를 구하고, 그 값을 모두 더했을 때 합이 최대가 되도록 셔츠를 배치하려고 한다.

예를 들어 첫 번째 선반에 6장짜리 더미와 9장짜리 더미가 있고, 두 번째 선반에 2장짜리 더미 하나가 있고, 세 번째 선반에 5장, 6장, 7장짜리 더미가 있다고 하자. 이때 구하는 합은 $\gcd(6, 9) + \gcd(2) + \gcd(5, 6, 7) = 3 + 2 + 1 = 6$이다.

모든 더미를 서로 다른 선반에 하나씩 놓으면 합이 최대가 된다는 것을 Bit도 바로 알아챘다. 하지만 게임을 더 재미있게 하려고 빈 선반이 아닌 선반에는 더미가 최소 $D$개 있어야 한다는 조건을 정했다. 빈 선반의 최대공약수는 $0$이다.

Bit은 셔츠의 순서를 크게 바꾸고 싶지 않다. 그래서 더미는 다음 규칙에 따라서만 옮긴다.

• 선반의 가장 오른쪽 더미를 바로 아래 선반의 가장 왼쪽으로 옮길 수 있다. 가장 아래 선반은 제외한다.
• 선반의 가장 왼쪽 더미를 바로 위 선반의 가장 오른쪽으로 옮길 수 있다. 가장 위 선반은 제외한다.

시간이 충분하고 더미를 선반 사이에서 몇 번이든 옮길 수 있을 때, Bit이 얻을 수 있는 최대공약수 합의 최댓값을 구하는 프로그램을 작성하라.

첫 줄에 선반 수 $N$, 더미의 총수 $M$, 빈 선반이 아닌 선반에 있어야 하는 더미 수의 최솟값 $D$가 주어진다. ($1 \le D \le M \le N \le 500\,000$)

다음 $N$개 줄에 선반 정보가 위에서 아래 순서로 주어진다. 각 줄은 선반의 더미 수 $K_i$ ($0 \le K_i \le M$)로 시작하고, 이어서 왼쪽에서 오른쪽 순서로 정수 $K_i$개 $X_{i,j}$ ($1 \le X_{i,j} \le 10^9$)가 주어진다. $X_{i,j}$는 그 더미에 있는 셔츠의 수이다.

얻을 수 있는 최대공약수 합의 최댓값을 한 줄에 정수로 출력한다.