Faster Than Light

Faster Than Light 비디오 게임에서 각 우주선은 평면 격자 위에 표현된다. 격자의 모든 칸은 한 변의 길이가 1인 정사각형이다. 일부 칸은 공격할 수 있는 우주선의 구역이고, 나머지 칸은 우주선에 속하지 않는다.

빔 무기는 공격 대상 우주선 위에 길이가 $L$인 선분을 그린다. 선분의 한쪽 끝은 공격 대상 우주선 구역의 내부나 경계 위에 있어야 한다. 그 밖에는 선분의 위치를 자유롭게 정할 수 있다. 다른 쪽 끝은 격자 바깥을 포함해 어디에 있어도 된다. 선분과 구역 칸(경계를 포함)이 한 점이라도 공유하면 그 구역은 피해를 입는다. 각 구역은 맞았을 때 얻는 양의 점수가 정해져 있다. 피해를 입은 구역들의 점수 합이 최대가 되는 선분의 위치를 구한다.

첫째 줄에 격자의 행 수와 열 수를 나타내는 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 30$).

둘째 줄에는 선분의 길이인 실수 $L$이 주어진다. 소수점 아래는 최대 두 자리이다 ($0.1 \le L \le 50$).

다음 $N$개의 줄에는 격자가 주어진다. 각 줄에는 정수가 $M$개 있다. $i$번째 줄의 $j$번째 수를 $a_{ij}$라 한다 ($0 \le a_{ij} \le 10^7$). $a_{ij} = 0$이면 빈 칸이다. $a_{ij} > 0$이면 우주선 구역이며, 맞히면 $a_{ij}$점을 얻는다.

우주선 구역은 적어도 하나 있다. 서로 다른 구역끼리는 연결되어 있지 않을 수 있다.

무기를 한 번 발사했을 때 얻을 수 있는 최대 점수를 정수 하나로 출력한다.

예제에서는 5점짜리 칸 두 개, 1점과 3점짜리 칸, 그리고 8점과 1점짜리 칸을 맞히도록 무기를 발사할 수 있다.