You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

赌神小 Y 赢得比赛，准备狂炫他最爱的巧克力，他的包里有块 $N \times M$ 的长方形巧克力，小 Y 想把巧克力全部分成 $1 \times1$ 的小正方形，以便小 Y 慢慢享用。

但巧克力本身并不均匀，因此从不同的线切下去要花不同的代价。而且对于一块巧克力，切割一次以后就被分割成两块，而且由于不能把这两块巧克力拼在一起然后一刀切成四块（容易切歪），所以只能两块分别再进行一次切割。现在小 Y 并不想花太多的力气，所以他来找你帮他求一求最小的代价。

输入格式

第一行包括 $N$ 和 $M$（$1 ≤ N，M ≤ 1000$），表示长 $N$ 行 $M$ 列的矩阵。

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

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

输出格式

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

样例

2 2
3
3

9

数据范围

对于 $60\%$ 的数据， $N,M \ \le\ 100$。

对于 $100\%$ 的数据， $N,M \ \le\ 1000$；$切割代价 \ \le\ 1000$。