比赛场次	75
比赛名称	10101115
比赛状态	已结束比赛成绩
开始时间	2010-11-15 08:15:00
结束时间	2010-11-15 11:30:47
开放分组	全部用户
组织者	cqw
注释介绍

题目名称	矩形分割
输入输出	`cut.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	10 简单对比

用户	结果	时间	内存	得分
gragon	AAAAAAAAAA	0.000 s	0.00 MiB	100
wo shi 刘畅	AAAAAAAAAA	0.000 s	0.00 MiB	100
郭乾乐	AAAAAAAAAA	0.000 s	0.00 MiB	100
Pom	AAAAAAAAAA	0.000 s	0.00 MiB	100
ZhouZn1	AAAAAAAAAA	0.000 s	0.00 MiB	100
Citron酱	AAAAAAAAAA	0.000 s	0.00 MiB	100
mate	AAAAAAAAAA	0.000 s	0.00 MiB	100
Achilles	AAWAAAAAAA	0.000 s	0.00 MiB	90
苏轼	AWWAAAAAAA	0.000 s	0.00 MiB	80
1102	AAAAAAATTT	0.000 s	0.00 MiB	70
lc	AAAAAAWWWW	0.000 s	0.00 MiB	60
sr-end	AAAAAAEEEE	0.000 s	0.00 MiB	60
王者自由	AAAAWAWWWW	0.000 s	0.00 MiB	50
nick09	AAAEEEEEEE	0.000 s	0.00 MiB	30
make	AATTTTTTTT	0.000 s	0.00 MiB	20
Des.	AWWWWWWWWA	0.000 s	0.00 MiB	20
maxiem	AWWAWWWWWW	0.000 s	0.00 MiB	20
.Xmz	AWAWWWWWWW	0.000 s	0.00 MiB	20
DeiTy	AWWWWWTTTT	0.000 s	0.00 MiB	10
wangwangdog	AWWWWWWWWW	0.000 s	0.00 MiB	10
ybh	AWWWWWWWWW	0.000 s	0.00 MiB	10
donny	AWWWWWWWWW	0.000 s	0.00 MiB	10
苏轼	AWWWWWWWWW	0.000 s	0.00 MiB	10
belong.zmx	AWWWWWWWWW	0.000 s	0.00 MiB	10
itachi	WWWWWWWWWW	0.000 s	0.00 MiB	0
reamb	WWWWWWWWWW	0.000 s	0.00 MiB	0
ZHZH	EEEEEEEEEE	0.000 s	0.00 MiB	0

1. 矩形分割

★☆ 输入文件：cut.in 输出文件：cut.out
时间限制：1 s 内存限制：128 MiB

Description

出于某些方面的需求，我们要把一块N×M的木板切成一个个1×1的小方块。

对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。

现在，给出从不同的线切割所要花的代价，求把整块木板分割成1×1块小方块所需要耗费的最小代价。

Input Format

输入文件第一行包括N和M，表示长N宽M的矩阵。

第二行包括N-1个非负整数，分别表示沿着N-1条横线切割的代价。

第三行包括M-1个非负整数，分别表示沿着M-1条竖线切割的代价。

Output Format

输出一个整数，表示最小代价。

Sample Input

2 2

3

3

Sample Output

9

Data Limit

对于60%的数据，有1 ≤ N ,M≤ 100；

对于100%的数据，有1 ≤ N,M ≤ 2000。