# Omara

Jadran ima doma veliko omaro, v njej pa še več majic iz različnih tekmovanj. Zato želi napraviti red.

Jadran želi urediti kupčke majic tako, da bo vsota največjih skupnih deliteljev (NSD) števil majic v vseh kupih na eni polici največja (če na kupu ni nobene majice, je NSD enak $0$). Prav tako pa ne želi premikati majic med kupi.

Na primer, če sta na prvi polici kupa s $6$ in $9$ majicami, na drugi polici kup z $2$ majicama ter na tretji polici kupi s $5$, $6$ in $7$ majicami je vsota NSD enaka $6$ (ker je $NSD(6,9) + NSD(2) + NSD(5,6,7) = 3 + 2 + 1 = 6$).

Jadran je našel zelo dolgočasen način, da najde največjo vsoto - vsak kup postavi na svojo polico. Zato se je odločil, da bo na vsaki polici $0$ ali vsaj $D$ kupov majic.

Ker so Jadranove majice že zložene po letnikih, si ne želi delati prevelikih sprememb. Zato premika kupe majic po naslednjih dveh pravilih:

* Kup na desnem koncu police lahko prestavi na polico pod njo in kup postavi na levo stran police
* Kup na levem koncu police lahko prestavi na polico nad njo in kup postavi na desno stran police.

Ker pa se je opravila lotil na deževno nedeljo, ima dovolj časa, da premika majice med policami v nedogled. Pomagaj mu poiskati največjo vsoto NSD, ki jo lahko dobi.

## Vhod

V prvi vrstici vhoda se nahajajo naravna števila $N$, $M$ in $D$ ($1 \leq D \leq M \leq N \leq 500000$) - število polic, število kupov majic v omari ter najmanjše število kupov majic na polici.

V naslednjih $N$ vrsticah se nahajajo opisi polic. V $i$-ti vrstici se nahaja celo število $K_i$ ($0 \leq K_i \leq M$) - število kupov na $i$-ti polici. Sledi mu $K_i$ naravnih števil $x_{i,j}$ ($1 \leq x_{i,j} \leq 10^9$) - število majic v $j$-tem kupu $i$-te police. Kupi so označeni od leve proti desni. Vsota $K_i$ je enaka $M$.

Vsa števila v vrstici so ločena s presledkom.

## Izhod

Izpiši največjo vsoto NSD ob upoštevanju zgornjih pravil.

## Primer

### Vhod

3 3 1
0
2 1 3
1 2

### Izhod
`6`

### Vhod

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

### Izhod
`5`

## Komentar

V prvem primeru ima Jadran 3 police s tremi kupi majic. Vsak kup lahko da na svojo polico, zato je vsota NSD enaka $1+3+2=6$.

V drugem primeru mora Jadran urediti kupe tako, da bosta na vsaki polici vsaj dva kupa ali pa mora polica ostati prazna.
Če postavi vse kupe na eno polico, dobi vsoto enako 1.
Če postavi kupe 4, 8 in 1 na eno polico in 3, 6 na drugo, dobi vsoto $1+3=4$.
Če postavi kupa 4 in 8 na eno polico ter kupe 1, 3 in 6 na drugo, dobi vsoto $4+1=5$.