AT_joi2015yo_d シルクロード (Silk Road)

商人JOI先生带着货物，从0号城市出发，丝绸之路包括起点和终点一共有N+1个城市。要求不超过M天内必须到达终点。一天的时间可以从一个城市到连续的下一个城市。从i-1城市到i城市距离是Di。 JOI先生在一个城市时，可以有以下选择： 移动：向下一个城市进发 休息：呆在原来的城市不动 沙漠天气变化无常，在天气很不好时，前进会遇到很多困难。我们把M天的第j(1

第一行2个整数N，M 连续N行每行一个整数Dj 连续M行每行一个整数Cj

一个整数，表示最小疲劳度

### Sample Explanation 1 入出力例 $ 1 $ において，溜まる疲労度の合計を最小にするように JOI 君が移動するには次のようにする． - $ 1 $ 日目は待機する． - $ 2 $ 日目に都市 $ 0 $ から都市 $ 1 $ へ移動する．このとき溜まる疲労度は $ 10\ \times\ 30\ =\ 300 $ である． - $ 3 $ 日目に都市 $ 1 $ から都市 $ 2 $ へ移動する．このとき溜まる疲労度は $ 25\ \times\ 15\ =\ 375 $ である． - $ 4 $ 日目は待機する． - $ 5 $ 日目に都市 $ 2 $ から都市 $ 3 $ へ移動する．このとき溜まる疲労度は $ 15\ \times\ 30\ =\ 450 $ である． JOI 君がこのように移動した場合に溜まる疲労度の合計は $ 300\ +\ 375\ +\ 450\ =\ 1\,125 $ である．これが最小値である． - - - - - -