D - Ratoneras

Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits: (details)

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.

Input

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.

Output

Imprima el mayor número de ratoneras que pueden quitarse.

Sample test(s)

Input
4 2 5 5 1 1 1 5 5 1 1 1 5 5 5 5 1 1
Output
36
Input
3 1 2 2 4 4 1 5 2 3 5
Output
13
Input
6 3 1 2 3 4 5 3 1 6 4 5 1 2 7 3 8 2 1 1 2 1 6 7 3 4 3 1 4 4 4 4 5 6 7 1 1 1
Output
89