#P9312. 选球

    ID: 5617 传统题 3000ms 888MiB 尝试: 13 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-最小割建模最大流最小割定理0/1 背包倒序更新避免重复使用自定义排序规则扫描中维护贡献

选球

题面翻译

题目翻译

有一些颜色为 [1,n][1,n] 的球,其中颜色为 ii 的球有 aia_i 个。此外,有 mm 个盒子,第 jj 个盒子能装 bjb_j 个球。

另外,对于所有的 1≤i≤n,1≤j≤m1\le i\le n,1\le j\le m,满足第 jj 个盒子最多装 (i×j)(i\times j) 个颜色为 ii 的球。求这 mm 个盒子最多能装多少个球。

输入格式

第一行两个数 n,mn,m。

第二行 nn 个数,表示 aia_i。

第三行 mm 个数,表示 bib_i。

数据范围

n≤500,m≤5×105,0≤ai,bi≤1012n\le 500,m\le 5\times 10^5,0\le a_i,b_i\le 10^{12}。

样例 #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