종이 접기 2

직사각형 종이가 한 장 있다. 종이는 $1 \times 1$ 크기의 칸으로 나뉘어 있고, 각 칸에는 정수가 하나씩 적혀 있다.

종이는 두 행 사이 또는 두 열 사이를 지나는 직선을 따라 접는다. 한 번 접으면 종이의 한쪽이 반대쪽 위로 포개지고, 두 칸이 겹친 자리의 수는 겹치기 전 두 수의 합이 된다. 이미 여러 겹으로 접혀 있는 부분은 층 전체가 함께 접힌다. 반대쪽 밖으로 나가 아무 칸과도 겹치지 않는 칸은 적힌 수를 그대로 유지한다. 접는 횟수에는 제한이 없고, 한 번도 접지 않아도 된다.

종이를 원하는 대로 접었을 때 한 칸에 적힐 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 종이의 세로 크기 $N$과 가로 크기 $M$이 주어진다. $N$과 $M$은 $6$ 이하의 자연수이다. 둘째 줄부터 $N$개의 줄에 각 줄마다 $M$개의 정수가 주어진다. 이 값은 절댓값이 $100$ 이하이다.

첫째 줄에 한 칸에 적힐 수 있는 수의 최댓값을 출력한다.