16119번 - Cherrypick

SNUPC(SNU Patisserie Cafe)에서는 유명한 케이크를 팔고 있다. 이 케이크는 N개의 행과 N개의 열로 나눌 수 있는 정사각형 모양이다. 그리고 이 케이크를 1 × 1 크기의 정사각형 조각 N²개로 잘랐을 때, 각 조각 위에 체리가 하나씩 올려져 있다. i행 j열 조각 위의 체리는 C_i,j만큼의 당도를 가지고 있다. 이 케이크는 한 번에 먹기에는 너무 크기 때문에, 각 변이 축에 평행하고 각 꼭짓점의 x좌표와 y좌표가 정수인 정사각형 모양으로 잘라내어 판매하고 있는데, 잘라낸 정사각형의 한 변의 길이를 X라고 했을 때, 잘라낸 조각을 X²원에 판매한다.

이 가게에 슈퍼 부자 Corea가 방문하였다. Corea는 이전 가게에서 이미 너무 많은 음식을 먹었기 때문에, 케이크를 산 다음 그 위에 있는 체리 중 가장 단 체리 한 조각만을 먹으려고 한다. 또, 이 케이크의 특정한 조각을 하나 골라서, 그 조각은 반드시 포함되도록 구매하려고 한다.

Corea는 돈을 낭비하는 것을 별로 좋아하지 않기 때문에, 자신이 먹게 될 체리의 당도에서 케이크를 사는데 내는 비용을 뺀 값을 최대화하려고 한다. 하지만 Corea는 그런 사소한 결정을 하는데 낭비할 시간이 없기 때문에, Corea가 케이크에 포함될 조각을 고를 동안 당신은 Corea가 선택할 수 있는 모든 경우의 수에 대해서 Corea가 먹게 될 체리의 당도에서 케이크의 비용을 뺀 값의 최댓값을 계산해야 한다.

첫 번째 줄에 전체 케이크의 행과 열의 길이 N(1 ≤ N ≤ 1,000)이 주어진다.

두 번째 줄부터 총 N개의 줄에 각각 N개의 정수 C_i,j (1 ≤ C_i,j ≤ 1,000)가 주어지는데, 이는 i행 j열 조각 위에 놓인 체리의 당도이다.

공백으로 구분된 N개의 정수를 N줄에 걸쳐 출력한다.

i번째 줄의 j번째 정수로 출력하는 값은 i행 j열 조각을 포함하도록 케이크를 구매했을 때 Corea가 먹게 될 체리의 당도에서 케이크의 비용을 뺀 값의 최댓값이다.