Con la llegada de la primavera, el pequeño Cayusín decidió restaurar el orden en su armario. En el armario hay ~N~ estantes largos, cada uno de los cuales puede guardar un gran número de pulóveres, los cuales Cayusín trajo de varias Olimpiadas de Informática.

Cayusín retomó unos de sus juegos de infancia: él desea reordenar las pilas de pulóveres de su armario tal que la suma del máximo común divisor (MCD) de las cantidades de pulóveres en las pilas de los estantes resulte tan grande como sea posible. (Asumiendo que si no hay pulóveres en un estante, entonces su MCD es igual a cero.) Acorde a las reglas del juego, está prohibido desplazar pullovers de una pila a otra.

Por ejemplo, si en el primer estante del armario hay una pila con 6 pulóveres y una pila con 9 pulóveres; en el segundo una pila de 2 pulóveres; y en el tercero pilas de 5, 6, y 7 pulóveres respectivamente, la suma de los MCD será igual a 6 (puesto que ~\mathrm{mcd}(6, 9) + \mathrm{mcd}(2) + \mathrm{mcd}(5, 6, 7) = 3 + 2 + 1 = 6~).

Cayusín inmediatamente se dio cuenta que para maximizar tal suma debe quitar una pila de pulóveres en cada estante. Por supuesto, esto será muy aburrido, así que decidió que cada estante debe estar vacío o contener al menos ~D~ pilas de pulóveres.

Cayusín no desea cambiar el orden de los pulóveres en su armario significativamente (puesto que los tienen ordenado por el año de participación en las competiciones y tipos de competiciones). Así que moverá las pilas completas acorde a las siguientes reglas:

• La pila de más a la derecha de cualquiera de los estantes puede moverse al estante que se localiza debajo de este (si existe) colocándose a la izquierda de todas las pilas que yacen en este estante;
• La pila de más a la izquierda de un estante puede moverse al estante localizado directamente arriba de este colocándose a la derecha de todas las que están en este estante.

Cayusín no tiene mucho tiempo, así que él no puede hacer cualquier número de tales operaciones, Ayúdelo a determinar la máxima suma de MCD que puede obtener como resultado.

Entrada

La primera línea contiene los números ~N, M y D (1 \leq D \leq M \leq N \leq 500\,000)~ — el número de estantes y pilas de pulóveres en el armario de Cayusín y el mínimo número de pilas en un estante.

Las próximas ~N~ líneas contienen la descripción de los estantes. La i-ésima línea contienen un entero ~K_i (1 \leq K_i \leq M)~ – el número de pilas que hay en el ~i~-ésimo estante, así como ~K_i~ enteros ~x_{ij} (1 \leq x_{ij} \leq 10^9)~ – el número de pulóveres en la ~j~-ésima pila del ~i~-ésimo estante (las pilas en los estantes se muestran en orden de izquierda a derecha).

La suma de todos los ~K_i~ es igual a ~M~.

Los números en las líneas están separados por espacio.

Salida

Imprima un simple entero, la máxima suma de los MCD la cual Cayusín puede obtener moviendo pilas de pulóveres por el método descrito anteriormente.

Ejemplos

Entrada 1

3 3 1
0
2 1 3
1 2

Salida 1

6

Explicación 1

Hay 3 estantes en el armario conteniendo 3 pilas de pulóveres, Cayusín puede poner cada pila en un estante separado, la suma de los MCD es ~1 + 3 + 2 = 6~.

Entrada 2

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

Salida 2

5

Explicación

Cayusín debe colocar las pilas en el armario de tal forma que cada estante haya al menos dos pilas de pulóveres, o el estante esté vacío. Puede colocar las 5 pilas en un estante y obtener la suma 1. Cayusín también puede colocar las pilas de 4, 8 y 1 pulóveres en un estante y la de 3 y 6 en otro. En este caso obtendrá la suma de MCD igual a ~1 + 3 = 4~. Y también puede colocar las de 4 y 8 pulóveres en un estante y las de 1, 3 y 6 en otro, obteniendo como resultado ~4 + 1 = 5~.