103326: [Atcoder]ABC332 G - Not Too Many Balls

Problem Statement

There are several balls. Each ball is one of the colors $1$, $2$, $\ldots$, $N$, and for each $i = 1, 2, \ldots, N$, there are $A_i$ balls of color $i$.

Additionally, there are $M$ boxes. For each $j = 1, 2, \ldots, M$, the $j$-th box can hold up to $B_j$ balls in total.

Here, for all pairs of integers $(i, j)$ satisfying $1 \leq i \leq N$ and $1 \leq j \leq M$, the $j$-th box may hold at most $(i \times j)$ balls of color $i$.

Print the maximum total number of balls that the $M$ boxes can hold.

Constraints

• All input values are integers.
• $1 \leq N \leq 500$
• $1 \leq M \leq 5 \times 10^5$
• $0 \leq A_i, B_i \leq 10^{12}$

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

Output

Print the answer.

Sample Input 1

2 3
8 10
4 3 8

Sample Output 1

14

You can do as follows to put a total of $14$ balls into the boxes while satisfying the conditions in the problem statement.

• For balls of color $1$, put one into the first box, one into the second box, and three into the third box.
• For balls of color $2$, put two into the first box, two into the second box, and five into the third box.

Sample Input 2

1 1
1000000000000
0

Sample Output 2

0

Sample Input 3

10 12
59 168 130 414 187 236 330 422 31 407
495 218 351 105 351 414 198 230 345 297 489 212

Sample Output 3

2270

问题描述

有一些球。 每个球都有颜色$1$、$2$、$\ldots$、$N$，对于每个$i = 1, 2, \ldots, N$，有$A_i$个颜色为$i$的球。

另外，有$M$个盒子。 对于每个$j = 1, 2, \ldots, M$，第$j$个盒子最多可以容纳$B_j$个球。

在这里，对于所有满足$1 \leq i \leq N$和$1 \leq j \leq M$的整数对$(i, j)$， 第$j$个盒子最多可以容纳$(i \times j)$个颜色为$i$的球。

输出$M$个盒子最多可以容纳的球的总数。

限制条件

• 所有输入值都是整数。
• $1 \leq N \leq 500$
• $1 \leq M \leq 5 \times 10^5$
• $0 \leq A_i, B_i \leq 10^{12}$

输入

输入从标准输入以以下格式给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

输出

输出答案。

样例输入1

2 3
8 10
4 3 8

样例输出1

14

你可以在满足问题描述中的条件的情况下，将总共$14$个球放入盒子中。

• 对于颜色为$1$的球，将一个放入第一个盒子，一个放入第二个盒子，三个放入第三个盒子。
• 对于颜色为$2$的球，将两个放入第一个盒子，两个放入第二个盒子，五个放入第三个盒子。

样例输入2

1 1
1000000000000
0

样例输出2

0

样例输入3

10 12
59 168 130 414 187 236 330 422 31 407
495 218 351 105 351 414 198 230 345 297 489 212

样例输出3

2270