배선 설계

Bytestreet 북쪽에는 $n$개의 건물이 일렬로 서 있다. 동쪽에서 서쪽 방향으로 $1,2,\dots,n$번 번호가 붙어 있으며, $i$번째 건물의 좌표는 $(i,1)$이다.

Bytestreet 남쪽에는 $n$개의 통신탑이 일렬로 서 있다. 동쪽에서 서쪽 방향으로 $1,2,\dots,n$번 번호가 붙어 있으며, $i$번째 통신탑의 좌표는 $(i,-1)$이다.

당신은 Byteland의 전기 기술자이며, 배선 계획을 설계하는 것이 임무다. 전선은 건물 하나와 통신탑 하나를 잇는 직선 선분으로, 양 끝점은 $(i,1)$과 $(j,-1)$이다. 건물과 통신탑의 각 쌍 사이에는 전선을 최대 하나만 연결할 수 있다. $i$번째 건물과 $j$번째 통신탑을 연결하면 건물 소유주로부터 $w_{i,j}$달러를 받는다.

건물에는 전선을 여러 개 연결할 수 있지만, $i$번째 건물에 전선을 하나라도 연결하려면 $u_i$달러를 내야 한다. 먼저 그곳에 장비를 설치해야 하기 때문이다. 마찬가지로 통신탑에도 전선을 여러 개 연결할 수 있지만, $i$번째 통신탑에 전선을 하나라도 연결하려면 $v_i$달러를 내야 한다. 두 전선은 끝점에서만 만날 수 있으며, 이는 합선을 막기 위함이다.

장비를 설치할 수 없는 곳에는 어떤 전선도 연결할 수 없다. 질의가 $q$개 주어진다. $i$번째 질의에서는 정수 $a_i$, $b_i$, $c_i$, $d_i$가 주어지며, 번호가 $[a_i, b_i]$ 범위인 건물과 $[c_i, d_i]$ 범위인 통신탑에만 장비를 설치할 수 있다. 각 질의마다 수익이 최대가 되는 배선 계획을 구하라.

아무것도 하지 않을 수 있으므로 답은 음수가 될 수 없다.

입력은 하나의 테스트 케이스로만 이루어진다.

첫째 줄에 건물(또는 통신탑)의 개수 $n$과 질의의 개수 $q$가 주어진다 ($1 \leq n \leq 500$, $1 \leq q \leq 300\,000$).

둘째 줄에는 각 건물에 장비를 설치하는 데 드는 비용 $u_1, u_2, \dots, u_n$이 주어진다 ($1 \leq u_i \leq 10\,000$).

셋째 줄에는 각 통신탑에 장비를 설치하는 데 드는 비용 $v_1, v_2, \dots, v_n$이 주어진다 ($1 \leq v_i \leq 10\,000$).

이어지는 $n$개의 줄에는 각각 정수 $n$개가 주어진다. $i$번째 줄의 $j$번째 정수는 $w_{i,j}$이며 ($1 \leq w_{i,j} \leq 10\,000$), $i$번째 건물과 $j$번째 통신탑을 연결했을 때 받는 금액이다.

이어지는 $q$개의 줄에는 각각 네 정수 $a_i$, $b_i$, $c_i$, $d_i$가 주어진다 ($1 \leq a_i \leq b_i \leq n$, $1 \leq c_i \leq d_i \leq n$). 이는 $i$번째 질의를 나타낸다.

각 질의에 대해, 얻을 수 있는 금액의 최댓값을 한 줄에 하나씩 출력한다.