MOJ Round #4Ended |
Hay unos ratones en el sótano de Fito. Tantos que llenó su sótano de ratoneras. Su sótano puede modelarse como una grilla de $N \times N$. Hay un número de ratoneras en cada celda y de cada celda se conoce este número. Al menos hay una ratonera en cada celda. Improbablemente, su amigo también descubrió ratones en su sótano. Sin embargo, este no tiene ratoneras, así que vino a pedirle algunas a Fito. Puesto que Fito ya colocó sus ratoneras en su sótano, necesita analizar qué hacer. Ellos decidieron quitar algunas ratoneras del sótano de Fito. Precisamente, en cada fila quitarán todas las ratoneras de exactamente $K$ celdas consecutivas . Después de hacer esto los ratones no pueden ser capaz de cruzar desde el lado izquierdo hacia el lado derecho del sótano o de arriba hacia abajo . Los ratones se mueven en las cuatro direcciones cardinales (arriba, abajo, izquierda y derecha) y solamente pueden pasar a través de las celdas que no tengan ratoneras en ellas. Calcule el mayor número de ratoneras que pueden quitarse del sótano de Fito.
La primera línea contiene dos enteros $N$ y $K$ $(2 \leq N \leq 250, 1 \leq K \leq \frac{N}{2})$, las dimensiones del sótano y el número de celdas consecutivas que se quitarán en cada fila.
Imprima el mayor número de ratoneras que pueden quitarse.