Score : $625$ points

问题描述

存在若干个球，每个球的颜色为 $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$ 个盒子最多能容纳的球的总数。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:19:06