题目描述

现有若干个球，每个球的颜色为$1, 2, \dots, N$中的一种，其中颜色$i$（$i = 1, 2, \dots, N$）的球共有$A_i$个。

此外，有$M$个盒子，其中第$j$个盒子（$j = 1, 2, \dots, M$）总共最多能容纳$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$

输出格式

输出$M$个盒子能容纳的球的最大总数。

样例输入1

2 3
8 10
4 3 8

样例输出1

14

样例解释1

可按如下方式放置球，使总放置数达到14且满足所有条件：

• 颜色1的球：在第一个盒子放1个、第二个盒子放1个、第三个盒子放3个；
• 颜色2的球：在第一个盒子放2个、第二个盒子放2个、第三个盒子放5个。

验证约束：

• 盒子容量限制：
  • 盒子1：1+2=3 ≤ 4；
  • 盒子2：1+2=3 ≤ 3；
  • 盒子3：3+5=8 ≤ 8；
• 颜色-盒子数量限制：
  • 颜色1在盒子j的数量 ≤ 1×j：1≤1×1、1≤1×2、3≤1×3；
  • 颜色2在盒子j的数量 ≤ 2×j：2≤2×1、2≤2×2、5≤2×3；
• 颜色总数限制：
  • 颜色1总放置数1+1+3=5 ≤ 8；
  • 颜色2总放置数2+2+5=9 ≤ 10。

样例输入2

1 1
1000000000000
0

样例输出2

0

样例解释2

唯一的盒子最多只能容纳0个球，因此总放置数为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