문제
퍼즐놀이를 좋아하는 철기는 도미노를 가지고 노는 것을 좋아한다. 철기는 N×M크기의 보드에 수들을 적어놓고, 그 위에 2×1, 혹은 1×2의 도미노를 덮으려 한다.
이 때, 절댓값(각 도미노가 덮는 두 수의 차이)의 총 합이 최대가 되도록 하려 한다. 하나의 칸에는 한 개의 도미노만 올려놓을 수 있으며, 도미노가 올려져있지 않은 칸이 생길 수도 있다. 뿐만 아니라, 두 수의 차이가 T보다 큰 경우에는 두 수 위에 도미노를 덮어놓을 수 없다.
아래와 같이 보드가 있다고 하자.
1 1
10 10
예를 들어 위의 2×2배열(T=9)을 두 가지 방법으로 덮을 수 있는데,
(1, 1), (10, 10)을 덮은 경우에는 덮인 수들의 차이의 총 합이 0(|1-1| + |10-10|)이 되지만, (1, 10), (1, 10)으로 덮으면 18(|1-10|+|1-10|)이 된다. 그리고 이 방법이 최적해이다.
입력
첫째 줄에 N, M(1 <= N, M <= 30), T(0 <= T <= 10,000,000)가 주어진다. 다음 N개의 줄에는 M개의 정수로 배열의 모양이 주어진다. 배열을 이루는 각각의 수는 절댓값이 1,000,000을 넘지 않는다.
출력
덮인 수들의 차이의 총 합을 출력한다.
예제
2 2 10
1 1
10 10
18
로그인해야 코드를 작성할 수 있어요.