Make Many Buri-Oden

2 secs 1024 MB
RedSpica's icon RedSpica

問題文

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

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

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

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

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

制約

  • 1N1051 \leq N \leq 10^5
  • 1ai1051 \leq a_i \leq 10^5
  • 1bi1051 \leq b_i \leq 10^5
  • 入力される値はすべて整数である

入力

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

NN
a1a_1a2a_2\cdotsaNa_N
b1b_1b2b_2\cdotsbNb_N

出力

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

サンプル

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

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

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

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

提出


Go (1.21)