AT_abc332_g [ABC332G] Not Too Many Balls

题目描述

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

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

但是，对于所有满足 $1 \leq i \leq N$ 且 $1 \leq j \leq M$ 的整数对 $(i, j)$，将颜色 $i$ 的球放入第 $j$ 个箱子的数量不能超过 $i \times j$ 个。

请输出可以放入 $M$ 个箱子中的球的最大总数。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 3
8 10
4 3 8

输出 #1

14

输入输出样例 #2

输入 #2

1 1
1000000000000
0

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 输入的值均为整数。
• $1 \leq N \leq 500$
• $1 \leq M \leq 5 \times 10^5$
• $0 \leq A_i, B_j \leq 10^{12}$

样例解释 1

如下方式放球可以在满足题目条件的情况下，将总共 $14$ 个球放入箱子中。

• 将颜色 $1$ 的球放入第 $1$ 个箱子 $1$ 个，第 $2$ 个箱子 $1$ 个，第 $3$ 个箱子 $3$ 个。
• 将颜色 $2$ 的球放入第 $1$ 个箱子 $2$ 个，第 $2$ 个箱子 $2$ 个，第 $3$ 个箱子 $5$ 个。

由 ChatGPT 4.1 翻译