일몰 감상 2

바이트 시(市)의 주민들은 자기 집 옥상에서 일몰 보기를 좋아한다. 일몰이 유난히 아름다운 날이면, 더 나은 전망을 얻을 수 있는 근처 건물의 옥상까지 찾아가는 사람도 있다.

도시는 한 변의 길이가 $n$인 정사각형 격자로 이루어져 있고, 건물은 각 격자점마다 하나씩 서 있다. 두 격자점 사이의 거리는 도시 거리(맨해튼 거리)로 잰다. 두 점 $(a_x, a_y)$와 $(b_x, b_y)$ 사이의 도시 거리는 다음과 같다.

$p((a_x, a_y), (b_x, b_y)) = |a_x - b_x| + |a_y - b_y|$

준은 새 집을 사려고 한다. 그는 일몰을 아주 좋아해서, 자기 집에서 도시 거리로 $k$ 이하만큼 떨어진 건물이라면 기꺼이 찾아간다.

각 격자점마다 그곳에 살 때 준이 도달할 수 있는 가장 높은 건물의 높이를 구하려고 한다. 즉, 모든 격자점에 대해 그 지점에서 도시 거리로 $k$ 이하만큼 떨어진 건물들 중 가장 높은 높이를 구한 뒤, 그 값들을 전부 더한 합을 출력한다.

첫째 줄에 세 자연수 $n$, $k$, $seed$가 공백 하나로 구분되어 주어진다 ($1 \le n \le 3000$, $1 \le k \le 1000$, $1 \le seed \le 1000$). $seed$는 도시의 건물 높이를 생성하는 데 쓰인다. 행과 열은 $0$번부터 번호를 매기며, $i$행 $j$열($0 \le i < n$, $0 \le j < n$)에 서 있는 건물의 높이는 다음과 같다.

$h(i, j) = (3^{i} + 5^{j} \cdot seed) \bmod 228$

각 격자점에 대해 도시 거리로 $k$ 이하만큼 떨어진 건물들 중 가장 높은 높이를 구하고, 이 최댓값들을 모든 격자점에 대해 더한 값을 한 줄에 출력한다. 건물 높이는 위 식에서 $228$로 나눈 나머지로 생성되지만, 최종 합에는 나머지 연산을 적용하지 않고 그대로 출력한다.