Nina has an $n\times n$ chessboard and $\boldsymbol{\mbox{k}}$ jumping rooks. Every cell of the chessboard is either blocked or free, and Nina can only put a single rook in any free cell. 

Two jumping rooks beat each other if they are either in the same row or in the same column and all cells between them are free (note that it's possible that there are some other rooks between them). More formally, if the first rook is in cell $(x,y_1)$ and the second rook is in cell $(x,y_2)$ (where $y_1\leq y_2$), then these two rooks beat each other if and only if $(x,y_1),(x,y_1+1),...,(x,y_2)$ are free. If the rooks are in cells $(x_{1},y)$ and $(x_2,y)$, then cells $(x_1,y),(x_1+1,y),...,(x_2,y)$ must all be free.

Given the configuration of the chessboard and some $\boldsymbol{\mbox{k}}$, help Nina place $\boldsymbol{\mbox{k}}$ jumping rooks in the chessboard's free cells such that the number of pairs of rooks that beat each other is minimal. Then print a single integer denoting the number of rooks that beat each other.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the size of the chessboard) and $\boldsymbol{\mbox{k}}$ (the number of rooks to place). 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains a string of $n$ characters describing each row in the chessboard. The $j^{th}$ character of the $i^{\mbox{th}}$ line is # if cell $(i,j)$ is blocked or . if the cell is free.

Constraints

$1\leq n\leq50$
It is guaranteed that $\boldsymbol{\mbox{k}}$ is less than the number of free cells in the chessboard.

Output Format

Print a single integer denoting the minimum possible number of pairs of rooks that beat each other.

Sample Input 0

3 4
...
...
...

Sample Output 0

2

Explanation 0 

For this input, one possible arrangement is:

o.o
.o.
..o

where each o is a jumping rook.

Sample Input 1

5 10
..#..
..#..
#####
..#..
..#..

Sample Output 1

4

Explanation 1 

For this input, one possible arrangement is:

.o#o.
oo#oo
#####
.o#o.
o.#.o

where each o is a jumping rook.

Difficulty: HARD
Tags: Graph algorithms

Starter code:

Solutions:
import os
import sys
import re
(n, k) = map(int, input().split())
chess = [[i for i in input()] for _ in range(n)]

def getVal(c):
	val = [[0] * n for _ in range(n)]
	max_val = 0
	for i in range(n):
		for j in range(n):
			if chess[i][j] == '#':
				val[i][j] = -1
			else:
				val[i][j] = cost(i, j, c, '.')
			max_val = max(max_val, val[i][j])
	return (val, max_val)

def cost(i, j, c, char):
	cout = 0
	if j + 1 < n:
		x = j + 1
		p = c[i][x]
		while p != '#' and x < n:
			p = c[i][x]
			if p == char:
				cout += 1
			x += 1
	if j - 1 >= 0:
		x = j - 1
		p = c[i][x]
		while p != '#' and x >= 0:
			p = c[i][x]
			if p == char:
				cout += 1
			x -= 1
	if i + 1 < n:
		x = i + 1
		p = c[x][j]
		while p != '#' and x < n:
			p = c[x][j]
			if p == char:
				cout += 1
			x += 1
	if i - 1 >= 0:
		x = i - 1
		p = c[x][j]
		while p != '#' and x >= 0:
			p = c[x][j]
			if p == char:
				cout += 1
			x -= 1
	return cout
(val, max_val) = getVal(chess)
curr_c = 0
remain = k
cout_tot = 0
while remain > 0:
	for v in range(max_val + 1):
		if remain == 0:
			break
		for i in range(n):
			if remain == 0:
				break
			for j in range(n):
				if remain == 0:
					break
				if val[i][j] == v and chess[i][j] == '.':
					if cost(i, j, chess, 'o') == curr_c:
						cout_tot += curr_c
						chess[i][j] = 'o'
						remain -= 1
	curr_c += 1
other_count = 0
for i in range(n):
	for j in range(n):
		if chess[i][j] == 'o':
			other_count += cost(i, j, chess, 'o')
print(int(other_count / 2))


import os
import sys
import re
(n, k) = map(int, input().split())
chess = [[i for i in input()] for _ in range(n)]

def getVal(c):
	val = [[0] * n for _ in range(n)]
	max_val = 0
	for i in range(n):
		for j in range(n):
			if chess[i][j] == '#':
				val[i][j] = -1
			else:
				val[i][j] = cost(i, j, c, '.')
			max_val = max(max_val, val[i][j])
	return (val, max_val)

def cost(i, j, c, char):
	cout = 0
	if j + 1 < n:
		x = j + 1
		p = c[i][x]
		while p != '#' and x < n:
			p = c[i][x]
			if p == char:
				cout += 1
			x += 1
	if j - 1 >= 0:
		x = j - 1
		p = c[i][x]
		while p != '#' and x >= 0:
			p = c[i][x]
			if p == char:
				cout += 1
			x -= 1
	if i + 1 < n:
		x = i + 1
		p = c[x][j]
		while p != '#' and x < n:
			p = c[x][j]
			if p == char:
				cout += 1
			x += 1
	if i - 1 >= 0:
		x = i - 1
		p = c[x][j]
		while p != '#' and x >= 0:
			p = c[x][j]
			if p == char:
				cout += 1
			x -= 1
	return cout
(val, max_val) = getVal(chess)
curr_c = 0
remain = k
cout_tot = 0
while remain > 0:
	for v in range(max_val + 1):
		if remain == 0:
			break
		for i in range(n):
			if remain == 0:
				break
			for j in range(n):
				if remain == 0:
					break
				if val[i][j] == v and chess[i][j] == '.':
					if cost(i, j, chess, 'o') == curr_c:
						cout_tot += curr_c
						chess[i][j] = 'o'
						remain -= 1
	curr_c += 1
other_count = 0
for i in range(n):
	for j in range(n):
		if chess[i][j] == 'o':
			other_count += cost(i, j, chess, 'o')
print(int(other_count / 2))