Suurimad ühistegurid

문제

Bit koristab oma riidekappi, kus tal on hulk programmeerimisvõistluste T-särke. Särgid on mitmel riiulil erineva kõrgusega virnades.

Bit on juba lapsest saadik armastanud suurima ühisteguriga seotud mänge ja otsustas paigutada särgid riiulitele nii, et kui ta vaatab virnades olevate särkide arve, leiab iga riiuli jaoks nende arvude suurima ühisteguri ja liidab siis nende ühistegurite väärtused kokku, on tulemus maksimaalne võimalik.

Näiteks kui tal on esimesel riiulil ühes virnas 6 ja teises 9 särki, teisel riiulil ainult üks 2 särgiga virn ja kolmandal riiulil kolm virna vastavalt 5, 6 ja 7 särgiga, siis on otsitav summa $\gcd (6,9)+\gcd (2)+\gcd (5,6,7)=3+2+1=6\backslash gcd(6,\; 9)\; +\; \backslash gcd(2)\; +\; \backslash gcd(5,\; 6,\; 7)\; =\; 3\; +\; 2\; +\; 1\; =\; 6$.

Muidugi sai Bit kohe aru, et maksimaalse summa saamiseks tuleks iga särgivirn eraldi riiulile panna. See oleks aga liiga lihtne ja et mäng oleks põnevam, otsustas ta, et igal riiulil peab olema kas vähemalt $DD$ virna või peab riiul olema täiesti tühi (ja tühja riiuli suurim ühistegur on $00$).

Lisaks ei taha Bit oma särkide järjekorda liiga palju muuta, sest need on tal võistluste ja aastate kaupa sorteeritud. Sellepärast tõstab ta särke ümber ainult järgmise reeglite kohaselt:

• riiuli parempoolseima virna võib tõsta vahetult all oleva riiuli vasakpoolseimaks (välja arvatud kõige alumise riiuli korral);
• riiuli vasakpoolseima virna võib tõsta vahetult ülal oleva riiuli parempoolseimaks (välja arvatud kõige ülemise riiuli korral).

Kirjutada programm, mis leiab maksimaalse ühistegurite summa, mille Bit saavutada võib, kui tal on palju aega ja ta võib särgivirnu ühelt riiulilt teisele tõsta kuitahes palju kordi.

입력

Tekstifaili esimesel real on riiulite arv $NN$, särgivirnade koguarv $MM$ ja mitte\-tühja riiuli virnade arvu miimimum $DD$ ($1\le D\le M\le N\le 5000001\; \backslash le\; D\; \backslash le\; M\; \backslash le\; N\; \backslash le\; 500\backslash ,000$).

Järgmisel $NN$ real on riiulite kirjeldused. Iga rea alguses on riiulil olevate särgivirnade arv $K_{i}K\_i$ ($0\le K_i\le M0\; \backslash le\; K\_i\; \backslash le\; M$) ja selle järel $K_{i}K\_i$ täisarvu $X_{i,j}X\_\{i,j\}$ ($1\le X_{i,j}\le {10}^{9}1\; \backslash le\; X\_\{i,j\}\; \backslash le\; 10^9$), mis näitavad, mitu särki igas virnas on. Riiulite kirjeldused on antud ülalt alla ja virnade kirjeldused vasakult paremale.

출력

Tekstifaili ainsale reale väljastada üks täisarv: maksimaalne ühistegurite summa, mille Bit saavutada võib.

3 3 1
0
2 1 3
1 2

6

6 5 2
2 4 8
1 1
0
0
0
2 3 6

5