Make Many Buri-Oden

2 secs 1024 MB
RedSpica

問題文


「強い日差しの中 入り江の向こうに広がる海原」

あさかくんは富山県に古くから伝わるおせち料理ぶりおでんを作りたいと思っています.
この料理は ぶり匹とおでん個からぶりおでん個を作ることができ,それ以外の方法でぶりおでんを作ることはできません.

あさかくんはおせちの食材を求めて魚津市にある漁港にやってきました.
漁港には個のお店があり,それぞれのお店ではおせち用のセットを販売しています. 個目のお店ではぶり匹とおでん個からなるセットを販売しています.つのお店で複数個のセットを買うこともできます.

あさかくんはできるだけ多くのぶりおでんを作りたいと思い,セットを複数個買うことのできる十分な資金を用意しましたが, 自転車で買い物に来てしまったためおせち用のセットを最大でもセットしか買えないことがわかりました.

あさかくんが最適に買い物をしたとき最大で何個のぶりおでんを作ることができるかを求めてください.

制約


  • 入力される値はすべて整数である

入力


入力は以下の形式で標準入力から与えられます.



出力


問題の答えを整数で出力せよ.

サンプル


入力1
3
1 5 3
4 2 1
出力1
6

個目のお店と個目のお店でセットをつずつ買うと合計でぶりを匹, おでんを個手に入れることができます.
これらの食材を用いてちょうど個のぶりおでんを作ることができ,これより多くのぶりおでんを作ることのできる買い方は存在しないためこれが答えとなります.

入力2
6
3 1 4 1 5 9
2 7 1 8 2 8
出力2
16

個目のお店で個のセットを買うと合計でぶりを匹,おでんを個手に入れることができます.
これらの食材を用いて個のぶりおでんを作ることができ,これが最大となります.同じお店で複数個のセットを買うことができることに注意してください.

提出


Go (1.14)