어린 파울렉의 아빠는 세계적으로 유명한 체스 그랜드마스터로 아들도 그의 발자취를 따라오길 바랍니다. 따라서 그는 아이의 어린 나이에도 불구하고 벌써 체스를 가르치기 시작했습니다. 안타깝게도 파울렉은 배우는 게 느리고 재능도 없는 듯 합니다.
첫 3일 동안 파울렉은 폰을 움직이는 방법을, 다음 8일 동안은 나이트를 움직이는 방법을 (하루에 하나씩) 배웠습니다. 현재 파울렉은 룩을 움직이는 방법을 배우고 있는데, 이건 쉽게 배워 이틀만 배우면 완전히 룩을 움직이는 방법을 습득할 것 같습니다. 어쨌든 첫 날 수업이 끝난 현재, 파울렉은 룩을 가로로 움직일 수 있게 됐습니다.
아직 파울렉은 다음 날 무엇을 배울지 몰라 룩은 다른 칸으로는 이동하지 못하고 같은 행에 있는 칸으로만 이동할 수 있다고 굳게 믿고 있습니다. 파울렉은 체스에는 재능이 없지만, 수학에는 재능이 있습니다.
그래서 새로 배운 지식을 바탕으로 게임을 만들었습니다. 파울렉은 스스로 (8x8일 필요는 없지만 정사각형인) 체스 판을 그리고 칸 하나에 하나씩 서로 다른 숫자를 적었습니다. 그리고 파울렉은 룩이 놓여 있는 칸의 수의 합이 가능한 최대가 되도록 룩을 놓습니다. 파울렉은 룩을 몇 개든 놓을 수 있습니다 (필요하면 집에 있는 다른 세트에서 가져오면 됩니다); 만약 룩을 하나도 놓지 않는다면, 합은 0이 됩니다. 게임이 너무 단순해지지 않도록, 파울렉은 룩끼리는 (현재 파울렉의 지식 속에서) 서로 공격할 수 없는 위치에 있어야 한다는 규칙을 만들었습니다.
체스판의 크기와 파울렉이 칸에 적은 수가 주어질 때, 주어진 규칙에 따라 룩을 놓았을 때 얻을 수 있는 합의 최댓값을 구합시다.
입력
첫 줄에 체스 판의 너비와 높이를 나타내는 하나의 정수 n (1 <= n <= 200)이 입력됩니다. 다음 n개의 줄은 체스 판 각 줄 칸에 적혀 있는 수를 나타냅니다. 따라서, (n개의 줄 중) i번째 줄에는 체스 판의 i번째 줄에 적혀 있는 값을 나타내는 (-1,000,000부터 1,000,000 범위의) n개의 정수가 주어집니다.
ez_code 4년 전 14
문제
어린 파울렉의 아빠는 세계적으로 유명한 체스 그랜드마스터로 아들도 그의 발자취를 따라오길 바랍니다. 따라서 그는 아이의 어린 나이에도 불구하고 벌써 체스를 가르치기 시작했습니다. 안타깝게도 파울렉은 배우는 게 느리고 재능도 없는 듯 합니다.
첫 3일 동안 파울렉은 폰을 움직이는 방법을, 다음 8일 동안은 나이트를 움직이는 방법을 (하루에 하나씩) 배웠습니다. 현재 파울렉은 룩을 움직이는 방법을 배우고 있는데, 이건 쉽게 배워 이틀만 배우면 완전히 룩을 움직이는 방법을 습득할 것 같습니다. 어쨌든 첫 날 수업이 끝난 현재, 파울렉은 룩을 가로로 움직일 수 있게 됐습니다.
아직 파울렉은 다음 날 무엇을 배울지 몰라 룩은 다른 칸으로는 이동하지 못하고 같은 행에 있는 칸으로만 이동할 수 있다고 굳게 믿고 있습니다. 파울렉은 체스에는 재능이 없지만, 수학에는 재능이 있습니다.
그래서 새로 배운 지식을 바탕으로 게임을 만들었습니다. 파울렉은 스스로 (8x8일 필요는 없지만 정사각형인) 체스 판을 그리고 칸 하나에 하나씩 서로 다른 숫자를 적었습니다. 그리고 파울렉은 룩이 놓여 있는 칸의 수의 합이 가능한 최대가 되도록 룩을 놓습니다. 파울렉은 룩을 몇 개든 놓을 수 있습니다 (필요하면 집에 있는 다른 세트에서 가져오면 됩니다); 만약 룩을 하나도 놓지 않는다면, 합은 0이 됩니다. 게임이 너무 단순해지지 않도록, 파울렉은 룩끼리는 (현재 파울렉의 지식 속에서) 서로 공격할 수 없는 위치에 있어야 한다는 규칙을 만들었습니다.
체스판의 크기와 파울렉이 칸에 적은 수가 주어질 때, 주어진 규칙에 따라 룩을 놓았을 때 얻을 수 있는 합의 최댓값을 구합시다.
입력
첫 줄에 체스 판의 너비와 높이를 나타내는 하나의 정수 n (1 <= n <= 200)이 입력됩니다. 다음 n개의 줄은 체스 판 각 줄 칸에 적혀 있는 수를 나타냅니다. 따라서, (n개의 줄 중) i번째 줄에는 체스 판의 i번째 줄에 적혀 있는 값을 나타내는 (-1,000,000부터 1,000,000 범위의) n개의 정수가 주어집니다.
출력
파울렉이 얻을 수 있는 최댓값을 나타내는 하나의 정수를 출력합니다.