数列を抑える COBOL(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ n の数列 a = (a_1, a_2, ..., a_n) および整数 k, 長さ n - k + 1 の数列 b = (b_1, b_2, ..., b_{n-k+1}) が与えられます。
今から、あなたは以下の操作を任意の回数行うことで、数列のすべての要素を 0 以下にしたいと考えています。
・ 1 ≦ x ≦ n - k + 1 を満たす整数 x を選ぶ。
・ a_x, a_{x+1}, ..., a_{x+k-1} の各要素をちょうど 1 だけ減らす。
・ この操作にかかるコストは b_x である。
そのような操作列のうち、コストの総和の最小値を求めてください。
- 入力される値
-
n k
a_1 a_2 ... a_n
b_1 b_2 ... b_{n-k+1}
・ 1 行目に、数列 a の長さを表す整数 n と整数 k が半角スペース区切りで与えられます。
・ 2 行目に、数列 a の要素 a_1, a_2, ..., a_n が半角スペース区切りで与えられます。
・ 3 行目に、数列 b の要素 b_1, b_2, ..., b_{n-k+1} が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 10
・ 1 ≦ k ≦ 5
・ 1 ≦ n - k + 1
・ 1 ≦ a_i ≦ 10 (1 ≦ i ≦ n)
・ 1 ≦ b_i ≦ 10 (1 ≦ i ≦ n - k + 1)
- 入力例1
-
5 2
1 2 3 4 5
5 1 2 3
- 出力例1
-
23
- 入力例2
-
5 5
10 10 10 10 10
10
- 出力例2
-
100
