シルクロード (Silk Road)

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

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

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

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

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

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

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

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

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

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

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

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

JOI 2015 · JCIOI · CC BY-SA 4.0