#arc0251. [arc025_1]ゴールドラッシュ

[arc025_1]ゴールドラッシュ

問題文

stove 君はとある平面世界の住人である。

ある日 stove 君は多くの金が取れる鉱山を砂漠とジャングルに発見した。

stove 君は 77 日間かけて鉱山採掘に取り組むことにした。

砂漠とジャングルは遠い位置関係にあるので、それぞれの日にはどちらか一方の鉱山でしか採掘できない。

その日の天候、気分に応じて採掘量が鉱山ごとに変化してしまうので、どちらの鉱山を選ぶべきかがその日毎に異なる場合がある。

それぞれの日においての採掘量が分かっているとき、最適に鉱山を選んだ場合に得られる金の量がいくらかを求めるプログラムを作成せよ。


入力

入力は以下の形式で標準入力から与えられる。

D1D_1 D2D_2 .. D7D_7 J1J_1 J2J_2 .. J7J_7

  • 11 行目には、砂漠の鉱山に関する情報を表す 77 個の整数が空白区切りで書かれている。このうち左から ii 番目の整数 Di(0Di2,000)D_i (0 ≦ D_i ≦ 2,000) は、ii 日目に砂漠の鉱山で採掘を行った場合に得られる金の量が DiD_i キログラムであることを表す。
  • 22 行目にはジャングルの鉱山に関する情報を表す 77 個の整数が空白区切りで書かれている。このうち左から ii 番目の整数 Ji(0Ji2,000)J_i (0 ≦ J_i ≦ 2,000) は、ii 日目にジャングルの鉱山で採掘を行った場合に得られる金の量が JiJ_i キログラムであることを表す。

出力

最適に鉱山を選んだ場合に得られる金の量を 11 行に出力せよ。出力の末尾にも改行を入れること。


入力例1


4 2 0 5 6 2 5
6 1 4 3 6 4 6

出力例1


33

以下のように行動すれば良い。

  • 11 日目にはジャングルの鉱山を選び、66 キログラムの金を得る。
  • 22 日目には砂漠の鉱山を選び、22 キログラムの金を得る。
  • 33 日目にはジャングルの鉱山を選び、44 キログラムの金を得る。
  • 44 日目には砂漠の鉱山を選び、55 キログラムの金を得る。
  • 55 日目には砂漠の鉱山を選び、66 キログラムの金を得る。
  • 66 日目にはジャングルの鉱山を選び、44 キログラムの金を得る。
  • 77 日目にはジャングルの鉱山を選び、66 キログラムの金を得る。

このように行動すると、66 + 22 + 44 + 55 + 66 + 44 + 66 = 3333 キログラムの金を得ることができる。なお、55 日目にジャングルの鉱山を選んでも同じ量を達成することができる。


入力例2


1 2 3 4 5 6 7
2 3 4 5 6 7 8

出力例2


35

ジャングル一択である。


入力例3


0 0 0 0 0 0 0
0 0 0 0 0 0 0

出力例3


0

この例の場合、金を得ることができない。金が出るという話はなんだったのだろうか。


入力例4


8 3 0 2 5 25 252
252 252 2 5 2 5 2

出力例4


793