Wiring Engineering

On the north side of Bytestreet, there are $n$ buildings standing in a row. They are labeled $1,2,\dots,n$ from east to west, and the coordinate of the $i$-th building is $(i,1)$.

On the south side of Bytestreet, there are $n$ communication towers standing in a row. They are labeled $1,2,\dots,n$ from east to west, and the coordinate of the $i$-th tower is $(i,-1)$.

You are an electrical engineer in Byteland. Your job is to design a wiring scheme. A wire connects one building and one tower as a straight segment from $(i,1)$ to $(j,-1)$. For each pair of building and tower, you can connect at most one wire. Connecting the $i$-th building with the $j$-th tower earns $w_{i,j}$ dollars from the building owner.

Each building can have multiple wires, but you must pay $u_i$ dollars to connect at least one wire to the $i$-th building, because you must first install equipment there. Likewise, each tower can have multiple wires, but you must pay $v_i$ dollars to connect at least one wire to the $i$-th tower. Two wires can only intersect at their endpoints, which prevents short circuits.

Some places cannot have equipment installed, so no wire can connect to them. You are given $q$ queries. In the $i$-th query, you get four integers $a_i$, $b_i$, $c_i$, and $d_i$. You can install equipment only in buildings with labels in $[a_i, b_i]$ and in towers with labels in $[c_i, d_i]$. For each query, find the wiring scheme that maximizes your earnings.

The answer cannot be negative, because you can choose to do nothing.

The input contains only a single test case.

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 500$, $1 \leq q \leq 300\,000$), the number of buildings (or towers) and the number of queries.

The second line contains $n$ integers $u_1, u_2, \dots, u_n$ ($1 \leq u_i \leq 10\,000$), the cost to install equipment in each building.

The third line contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \leq v_i \leq 10\,000$), the cost to install equipment in each tower.

Each of the next $n$ lines contains $n$ integers. The $j$-th integer on the $i$-th line is $w_{i,j}$ ($1 \leq w_{i,j} \leq 10\,000$), the money you get for connecting the $i$-th building with the $j$-th tower.

Each of the next $q$ lines contains four integers $a_i$, $b_i$, $c_i$, and $d_i$ ($1 \leq a_i \leq b_i \leq n$, $1 \leq c_i \leq d_i \leq n$), describing the $i$-th query.

For each query, print a single line containing the maximum amount of dollars you can earn.