Migrated from Lutece 1347 柱爷的矩阵

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

柱爷能干这么多大事，与他喜爱玩弄矩阵是分不开的。

有一天柱爷创造了一个$N$行$M$列的的矩阵A，因为一个个造数据太麻烦，所以柱爷只搞了第一列的数据$A_{i,1},1 \leq i \leq N$，其他数据由$A_{i,j}=max(A_{i,j-1}-B_i,0),1 \leq i \leq N,2 \leq j \leq M$ 生成。

那么问题来了，柱爷想每行每列取不超过1个数，请问最大的和是多少。

Input

输入包括3行

第一行 2个数$N,M$

第二行 N个数$A_{i,1}$

第三行 N个数$B_i$

数据保证：

• $1 \leq M \leq N \leq 1000$

• $1 \leq A_{i,1} \leq 10^6$

• $1 \leq B_i \leq A_{i,1}$

Output

输出一个数，即答案

Samples

2 1
6 8 
1 5

8

4 3
5 9 10 3 
1 6 7 3

16

Note

对于样例2

矩阵A为

$$\begin{bmatrix} 5 & 4 & \underline 3\\ 9 & \underline 3 & 0\\ \underline {10} & 3 & 0\\ 3 & 0 & 0 \end{bmatrix} $$

$10+3+3=16$

Resources

2016 UESTC Training for Dynamic Programming