| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 1024 MB | 2 | 1 | 1 | 50.000% |
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