패널 최적화(Hard)

이 문제는 패널 최적화(Easy)와 $N$ 제한만 다른 상위 문제이고, 패널 최적화(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

근수의 태양광 패널은 $N \times N$ 크기의 격자판으로 이루어져 있다. $(i, j)$에 위치한 격자의 초기 전압은 $A_{ij}$로 주어지며, 이 격자의 전압을 $1$씩 증가시키거나 감소시킬 때 마다 $B_{ij}$만큼의 에너지가 소모된다.

근수는 초기에 $0$의 에너지를 가지고 있다. 근수는 현재 에너지의 값과 관계없이 각 격자의 전압을 원하는 만큼 올리거나 낮출 수 있다. 격자의 전압 조정이 끝나면, 격자판에서 인접한 두 격자들 간의 전압 상태에 따라 에너지를 얻거나 잃을 수 있다. 여기서 인접한 격자는 상하 좌우로 연결된 격자를 의미한다.

에너지는 다음과 같은 조건에 따라 얻거나 잃는다.

• 두 인접한 격자의 전압 부호가 한쪽이 양수이고 다른 한쪽이 음수면 두 격자 간의 에너지 흐름이 만들어져서 최종 에너지가 $4K$만큼 올라간다.
• 한 격자의 전압이 $0$이고 다른 격자의 전압이 양수 또는 음수일 경우에는 아무 일도 일어나지 않는다.
• 두 격자의 전압이 모두 $0$이면, 두 격자는 방전되기 시작하여서 최종 에너지가 $2K$만큼 줄어든다.
• 두 인접한 격자의 전압 부호가 둘 다 양수거나 둘 다 음수면 두 격자가 서로 과부하 되어서 최종 에너지가 $4K$만큼 줄어든다.

즉 두 격자의 전압 부호에 따른 에너지 변화는 다음과 같다.

근수의 목표는 격자판들의 전압을 잘 조절하여 최종 에너지를 최대화하는 것이다. 근수가 얻을 수 있는 최종 에너지의 최댓값을 구해보자.

첫 번째 줄에는 두 개의 정수 $ N $과 $ K $가 주어진다. $( 1 \leq N \leq 50, 0 \leq K \leq 1\,000 )$

그 다음 $ N $개의 줄에는 각각 $ N $개의 정수 $ A_{ij} $가 주어진다. $( -10 \leq A_{ij} \leq 10 )$

그 다음 $ N $개의 줄에는 각각 $ N $개의 정수 $ B_{ij} $가 주어진다. $( 0 \leq B_{ij} \leq 1\,000 )$

최종 에너지의 최댓값을 출력한다.