問題
ココア「チノちゃ〜ん！大変だよ〜！」
チノ「どうしたんですかココアさん？」
ココア「お客さんがたくさん来ちゃった！きっと全員は入りきらないよう＞＜」
チノ「わかりました。では、できるだけ大勢の方が店内に入れるようにしましょう」
ココア「りょーかい！でも、数人で来てるお客さんをばらばらに座らせるのはよくないよね！」
チノ「そうですね……。同じ席に座れなかったら、せめて隣り合っている席に座ってもらいましょう。あと、気を遣わせるのも悪いですし、相席もやめておきましょうか」
ココア「そうだね！よーしっ、わたし、がんばっちゃうよー！」
チノ「ココアさん、張り切りすぎです……」
入力
N M c1 c2 c3 ... cN t1 t2 t3 ... tM
１行目には、すべてのお客さん一行の数 N と店内の席の数 M が与えられる。
２行目には、 i 番目のお客さん一行を構成する人数 ci が N 個与えられる。
３行目には、 j 番目の席に座ることができる人数 tj が M 個与えられる。 j 番目の席は j-1 番目の席と j+1 番目の席と隣り合っている。ただし、１番目の席と M 番目の席には、それぞれ隣り合う席はただ１つしかない。
出力
入店できる人数の最大値を出力する。
制約
すべての入力ケースについて以下を満たす。
- 1 ≦ N ≦ 100
- 1 ≦ M ≦ 15
- 1 ≦ ci ≦ 108
- 1 ≦ ti ≦ 108
入出力例
入力例
10 3 3 2 5 1 4 6 4 2 4 1 5 10 2
5 10 3 3 3 2 1 4 2 3 4 2 3 5 2 2 2
出力例
13
12
余談
難しい問題つくる予定だったのに、くそ簡単になった感な可能性が否めない。