JOI logo
第14回日本情報オリンピック 予選4

2014年12月14日
情報オリンピック日本委員会

問題
   シルクロード (Silk Road)

問題

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

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

貿易商である JOI 君は,都市 0 から出発して,都市を順番に経由し,都市 N まで絹を運ぶことになった.都市 0 から都市 N まで M 日以内に移動しなければならない.JOI 君は,それぞれの日の行動として,以下の 2 つのうちいずれか 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 行で出力せよ.

入出力例

入力例 1 入力例 2
3 5
10
25
15
50
30
15
40
30
  
2 6
99
20
490
612
515
131
931
1000
  
 
出力例 1 出力例 2
1125
   
31589
  

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

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

※各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.


採点用データ

入力データ 入力1 入力2 入力3 入力4 入力5