크리스털의 파괴

옛날 옛적에 Zenyk는 친구들을 위해 새로운 마법 게임을 생각해 냈다. 그는 $n \times m$ 크기의 보드를 가져와 그 위에 크리스털 $k$개를 놓았다. 그다음 보드 위에 폭탄 $b$개도 놓았다.

폭탄이 터지면 각 폭탄은 자신이 있는 행 또는 열에 있는 모든 크리스털을 파괴한다. 또한 선택한 방향에 있는 모든 폭탄도 함께 터뜨린다. 각 폭탄의 폭발 방향(행 또는 열)은 친구들이 정한다. 폭탄마다 방향이 다를 수 있다.

게임의 목표는 처음 터뜨릴 폭탄과 폭발 방향을 골라, 파괴되는 크리스털의 수가 최대가 되도록 하는 것이다.

첫 줄에는 정수 네 개 $n$, $m$, $k$, $b$가 주어진다 ($1 \le n, m \le 3000$, $0 \le k + b \le n \times m$). $n$과 $m$은 보드의 행 수와 열 수, $k$는 크리스털의 수, $b$는 폭탄의 수이다.

다음 $n$줄에는 보드가 한 줄에 $m$개의 문자로 주어진다:

• "."은 빈 칸,
• "k"는 크리스털,
• "b"는 폭탄이다.

파괴되는 크리스털 수의 최댓값을 정수 하나로 출력한다.