No.39 シルクロード (Silk Road)

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

現在カザフスタンがある地域には，古くは「シルクロード」と呼ばれる交易路があった．

シルクロード上には N + 1 個の都市があり，西から順に都市 0, 都市 1, ... , 都市 N と番号がつけられている．都市 i - 1 と都市 i の間の距離 (1 ≦ i ≦ N) は Di である．

貿易商である JOI 君は，都市 0 から出発して，都市を順番に経由し，都市 N まで絹を運ぶことになった．都市 0 から都市 N まで M 日以内に移動しなければならない．JOI 君は，それぞれの日の行動として，以下の 2 つのうちいずれか 1 つを選ぶ．

• 移動： 現在の都市から 1 つ東の都市へ 1 日かけて移動する．現在都市 i - 1 (1 ≦ i ≦ N) にいる場合は，都市 i に移動する．
• 待機： 移動を行わず，現在いる都市で 1 日待機する．

移動は大変であり，移動するたびに疲労度が溜まっていく．シルクロードでは日毎に天候の変動があり，天候が悪い日ほど移動には苦労を要する．

JOI 君が絹を運ぶのに使える M 日間のうち j 日目 (1 ≦ j ≦ M) の天候の悪さは Cj であることが分かっている．都市 i - 1 から都市 i (1 ≦ i ≦ N) に j 日目 (1 ≦ j ≦ M) に移動する場合，疲労度が Di × Cj だけ溜まってしまう．移動を行わず待機している日は疲労度は溜まらない．

JOI 君は，それぞれの日の行動をうまく選ぶことで，できるだけ疲労度を溜めずに移動したい．JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を求めよ．

入力

入力は 1 + N + M 行からなる．

1 行目には，2 つの整数 N, M (1 ≦ N ≦ M ≦ 1000) が空白を区切りとして書かれている．これは，シルクロードが N + 1 個の都市からなり，JOI 君が絹を都市 0 から都市 N まで M 日以内に運ばなければならないことを表す．

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，整数 Di (1 ≦ Di ≦ 1000) が書かれている．これは，都市 i - 1 と都市 i の間の距離が Di であることを表す．

続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，整数 Cj (1 ≦ Cj ≦ 1000) が書かれている．これは，j 日目の天候の悪さが Cj であることを表す．

出力

JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を 1 行で出力せよ．

入出力例

3 5
10
25
15
50
30
15
40
30

1125

入出力例 1 において，溜まる疲労度の合計を最小にするように JOI 君が移動するには次のようにする．

• 1 日目は待機する．
• 2 日目に都市 0 から都市 1 へ移動する．このとき溜まる疲労度は 10 × 30 = 300 である．
• 3 日目に都市 1 から都市 2 へ移動する．このとき溜まる疲労度は 25 × 15 = 375 である．
• 4 日目は待機する．
• 5 日目に都市 2 から都市 3 へ移動する．このとき溜まる疲労度は 15 × 30 = 450 である．

JOI 君がこのように移動した場合に溜まる疲労度の合計は 300 + 375 + 450 = 1125 である．これが最小値である．

2 6
99
20
490
612
515
131
931
1000

31589