F - Transfer Plan
Ceylon
2
s
1024
MB
100
点
問題文
TSGは、駒場キャンパスに部室があり、そこには $M$ 個の荷物があります。ここで、$i$ 番目の荷物の重さは $W_i$ です。
あなたの目標は、$M$ 個の荷物すべてを $N$ 日以内に本郷キャンパスに運ぶことです。
ただし、部室は狭いので荷物は $1$ 番目から順に運ぶことしかできず、$1$ 日に運ぶことのできる荷物の個数は $K$ 個までです。
また、日ごとに運ぶことの大変さが決まっており、具体的には $i$ 日目はその日運ぶ荷物の重さの総和の $A_i$ 倍の大変さがかかります。
$N$ 日間で $M$ 個の荷物を運びきるとき、$N$ 日間の大変さの総和の最小値を求めてください。
制約
- $1 \leq N,M \leq 5\times 10^3$
- $\lceil \frac{M}{N} \rceil \leq K \leq M$
- $1 \leq W_i \leq 10^7$
- $1 \leq A_i \leq 10^7$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N\ M\ K$
$A_1\ A_2\ \ldots\ A_N$
$W_1\ W_2\ \ldots\ W_M$
出力
大変さの総和の最小値を一行に出力せよ。
入力例 1
3 4 2
3 2 4
5 1 6 2
出力例 1
34
$1$ 番目の荷物と $2$ 番目の荷物を $1$ 日目に、$3$ 番目の荷物と $4$ 番目の荷物を $2$ 日目に運ぶ時の大変さ $(5+1)\times3+(6+2)\times2=34$ が大変さの取りうる最小値です。
入力例 2
5 5 1
1 2 3 4 5
9 5 3 8 1
出力例 2
65
$K=1$ なので、毎日 $1$ つずつ荷物を運ぶほかありません。
入力例 3
10 15 3
23 19 5 37 9 17 44 27 4 18
47 32 2 45 4 6 12 34 57 11 87 92 6 27 18
出力例 3
4263