26259번 - 백룸

은소마는 현재 알 수 없는 방에 갇혀 있다. 각 방에는 한 개의 수가 적혀 있고, 아래쪽, 오른쪽으로 향하는 문만 열려, 그 방향으로만 갈 수 있다고 한다. 그런데, 중간에 큰 벽 한 개가 가로막고 있어 문이 없는 경우도 있다. 은소마는 불안한 마음에 지나온 수들을 모두 더하며 오른쪽 맨 아래 마지막 방까지 나아가려고 한다. 현재 은소마는 가장 왼쪽 위 방에 있다. 은소마가 마지막 방에 도착할 때까지 수를 더해서 얻을 수 있는 합의 최댓값은 얼마일까?

첫 번째 줄에 방의 크기 $N$, $M$이 주어진다. $(2 \le N,M \le 1000)$

두 번째 줄부터 $N$개의 줄에 각 방에 적혀 있는 수 $a_{i,1}, a_{i,2}, \cdots, a_{i, M}$이 공백으로 구분되어 주어진다. $(-1000 \le a_{i,j} \le 1000)$

벽은 직선으로 주어지며, 혼동을 방지하기 위해 방 꼭짓점에 다음과 같이 번호를 부여한다.

$N+2$ 번째 줄에 $x_1, y_1, x_2, y_2$가 공백으로 구분되어 주어진다. ($0 \le x_1, x_2 \le N;$ $0 \le y_1, y_2 \le M;$ $x_1=x_2$ 또는 $y_1=y_2)$ 이는 $(x_1, y_1)$부터 $(x_2, y_2)$까지 벽이 있음을 의미한다. 벽은 없을 수도 있다. 이때는 $(x_1,y_1) = (x_2,y_2)$으로 주어진다.

입력으로 주어지는 모든 수는 정수이다.

마지막 방에 도착했을 때, 은소마가 얻을 수 있는 합의 최댓값을 출력한다. 영원히 마지막 방에 도달할 수 없다면, "Entity"를 출력한다.