/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
いくつかのボールがあります。 各ボールは色 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 個の箱の中に入れることができるボールの合計個数の最大値を出力してください。
制約
- 入力される値は全て整数
- 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 のボールを、1 番目の箱に 1 個、2 番目の箱に 1 個、3 番目の箱に 3 個入れる。
- 色 2 のボールを、1 番目の箱に 2 個、2 番目の箱に 2 個、3 番目の箱に 5 個入れる。
入力例 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
Score : 625 points
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