配点 : $600$ 点

問題文

リスの直大君は、 $N$ 個のドングリを持っています。 ある日直大君は、複数の貴金属取引所に行くことでドングリを増やすことにしました。

直大君は次のように行動します。

1. $N$ 個のドングリを持って巣から出る。
2. 取引所 $A$ に行く。
3. 取引所 $B$ に行く。
4. 取引所 $A$ に行く。
5. 巣に帰る。

取引所 $X(X=A,B)$ では、以下の操作を任意の順序で任意の整数回行うことができます(一度も行わなくてもよいです)。

• ドングリ $g_{X}$ 個を失う。金 $1$ グラムを得る。
• ドングリ $g_{X}$ 個を得る。金 $1$ グラムを失う。
• ドングリ $s_{X}$ 個を失う。銀 $1$ グラムを得る。
• ドングリ $s_{X}$ 個を得る。銀 $1$ グラムを失う。
• ドングリ $b_{X}$ 個を失う。銅 $1$ グラムを得る。
• ドングリ $b_{X}$ 個を得る。銅 $1$ グラムを失う。

もちろん、直大君の持っているドングリ、金、銀、銅のいずれかの数が負の量になるような操作を行うことはできません。

直大君が巣に持ち帰れるドングリの数は最大いくつになるでしょうか。 直大君はリスなので、巣に持ち帰った金、銀、銅は全くの無価値であることに注意して下さい。

制約

• $1 \leqq N \leqq 5000$
• $1 \leqq g_{X} \leqq 5000$
• $1 \leqq s_{X} \leqq 5000$
• $1 \leqq b_{X} \leqq 5000$
• 入力は全て整数である。

入力

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

$N$

$g_A$ $s_A$ $b_A$

$g_B$ $s_B$ $b_B$

出力

直大君が巣に持ち帰れるドングリの数の最大値を出力してください。

23
1 1 1
2 1 1

46

下記のようにすることで、ドングリ $46$ 個を巣に持ち帰れます。

• 取引所 $A$ でドングリ $23$ 個を金 $23$ グラムにする。 {ドングリ、金、銀、銅}={ $0,23,0,0$ }
• 取引所 $B$ で金 $23$ グラムをドングリ $46$個 にする。{ドングリ、金、銀、銅}={ $46,0,0,0$ }
• 取引所 $A$ では何もしない。{ドングリ、金、銀、銅}={ $46,0,0,0$ }

$47$ 個以上のドングリを得ることはできないため、答えは $46$ です。