在 Bytestreet 的北侧，有 $n$ 座建筑物从东向西依次排列，编号为 $1, 2, \dots, n$。第 $i$ 座建筑物的坐标为 $(i, 1)$。

在 Bytestreet 的南侧，有 $n$ 座通信塔从东向西依次排列，编号为 $1, 2, \dots, n$。第 $i$ 座通信塔的坐标为 $(i, -1)$。

你是 Byteland 的一名电气工程师，你的工作是设计一套布线方案。电线可用于连接建筑物和通信塔。每条连接沿直线延伸。对于每一对建筑物和通信塔，你最多可以在它们之间连接一条电线。当你使用电线连接第 $i$ 座建筑物和第 $j$ 座通信塔时，你将从建筑物所有者那里获得 $w_{i,j}$ 美元，该电线可视为连接 $(i, 1)$ 和 $(j, -1)$ 的线段。

每座建筑物可以连接多条电线，但如果你想在第 $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 \le n \le 500, 1 \le q \le 300\,000$)，分别表示建筑物（或通信塔）的数量和询问次数。

第二行包含 $n$ 个整数 $u_1, u_2, \dots, u_n$ ($1 \le u_i \le 10\,000$)，表示在每座建筑物中安装设备的成本。

第三行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10\,000$)，表示在每座通信塔中安装设备的成本。

接下来的 $n$ 行中，第 $i$ 行 ($1 \le i \le n$) 包含 $n$ 个整数 $w_{i,1}, w_{i,2}, \dots, w_{i,n}$ ($1 \le w_{i,j} \le 10\,000$)，描述连接第 $i$ 座建筑物和第 $j$ 座通信塔所能获得的收益。

接下来的 $q$ 行中，第 $i$ 行 ($1 \le i \le q$) 包含四个整数 $a_i, b_i, c_i$ 和 $d_i$ ($1 \le a_i \le b_i \le n, 1 \le c_i \le d_i \le n$)，描述第 $i$ 次询问。

输出格式

对于每次询问，输出一行包含一个整数，表示你可以获得的最大美元金额。

样例

输入 1

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

输出 1

8
5
1
7