408996: GYM103409 L Wiring Engineering

On the north side of Bytestreet, there are $$$n$$$ buildings standing sequentially one next to the other, labeled by $$$1,2,\dots,n$$$ from east to west. The coordinate of the $$$i$$$-th building is $$$(i,1)$$$.

On the south side of Bytestreet, there are $$$n$$$ communication towers standing sequentially one next to the other, labeled by $$$1,2,\dots,n$$$ from east to west. 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 can be used to connect a building and a tower. Each connection runs along a straight line. For each pair of building and tower, you can connect at most one wire between them. When you use a wire to connect the $$$i$$$-th building with the $$$j$$$-th tower, you will get $$$w_{i,j}$$$ dollars from the owner of the building, and the wire can be regarded as a segment connecting $$$(i,1)$$$ and $$$(j,-1)$$$.

Each building can be connected with multiple wires, but you need to pay $$$u_i$$$ dollars if you want to connect at least one wire to the $$$i$$$-th building, because you should first install equipment in that place. For the same reason, each tower can be connected with multiple wires, but you also need to pay $$$v_i$$$ dollars if you want to connect at least one wire to the $$$i$$$-th tower. What is more, two wires can only intersect at their endpoints, in order to prevent short-circuit.

Unfortunately, it is impossible to install equipment in some places, so they can not be connected with any wire. You will be given $$$q$$$ queries, in the $$$i$$$-th query, you will be given four integers $$$a_i,b_i,c_i$$$ and $$$d_i$$$, which means you can only install equipment in buildings whose label is in $$$[a_i,b_i]$$$, and you can only install equipment in towers whose label is in $$$[c_i,d_i]$$$. Your task is to find a wiring scheme to make money optimally. Note that the answer can't be negative because you can choose to do nothing.

The input contains only a single case.

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n\leq 500$$$, $$$1\leq q \leq 300\,000$$$), denoting 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$$$), denoting 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$$$), denoting the cost to install equipment in each tower.

In the next $$$n$$$ lines, the $$$i$$$-th line $$$(1 \le i \le n)$$$ contains $$$n$$$ integers $$$w_{i,1},w_{i,2},\dots,w_{i,n}$$$ ($$$1\le w_{i,j}\leq 10\,000$$$), describing how much money you can get if you connect the $$$i$$$-th building with the $$$j$$$-th tower.

In the next $$$q$$$ lines, the $$$i$$$-th line $$$(1 \le i \le q)$$$ 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 an integer, denoting the maximum amount of dollars you can earn.

3 4
1 2 1
2 1 2
1 2 3
4 5 6
3 2 1
1 3 1 3
2 3 1 2
1 1 2 3
1 2 2 3

8
5
1
7