패널 최적화(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 1000$)

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

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

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