题目描述

松鼠直大君有 $N$ 个橡子。一天，为了获得更多的橡子，他决定去几家贵金属交易所做几笔交易。

他计划这么做：

1. 拿着 $N$ 个橡子离开巢穴；
2. 到交易所 $A$ 做几笔交易；
3. 到交易所 $B$ 做几笔交易；
4. 再到交易所 $A$ 做几笔交易；
5. 回巢穴。

在交易所 $X$ $(X\ =\ A,\ B)$，他可以以任意顺序完成任意整数笔（可能为零）如下的交易：

• 花费 $g_{X}$ 个橡子买来 $1$ 克金；
• 花费 $1$ 克金买来 $g_{X}$ 个橡子；
• 花费 $s_{X}$ 个橡子买来 $1$ 克银；
• 花费 $1$ 克银买来 $s_{X}$ 个橡子；
• 花费 $b_{X}$ 个橡子买来 $1$ 克铜；
• 花费 $1$ 克铜买来 $b_{X}$ 个橡子。

当然，他不能在橡子不够时购买金、银或铜；也不能在金、银或铜不够时购买橡子。

请求出他最多能带多少橡子回巢穴。注意，金、银或铜即使被带回巢穴也是无意义的，因为他只是一只松鼠。

输入格式

从标准输入中按以下格式读入：

$N$
$g_A$ $s_A$ $b_A$
$g_B$ $s_B$ $b_B$

输出格式

一行一个整数，代表直大君能带回巢穴的最大橡子数。

样例 #1

样例输入 #1

23
1 1 1
2 1 1

样例输出 #1

46

提示

数据范围

• $1\ \leq\ N\ \leq\ 5000$
• $1\ \leq\ g_{X}\ \leq\ 5000$
• $1\ \leq\ s_{X}\ \leq\ 5000$
• $1\ \leq\ b_{X}\ \leq\ 5000$
• 所有输入的值都是整数。

样例 #1 解释

他可以拿 $46$ 个橡子回巢穴：

• 在交易所 $A$，用 $23$ 个橡子买 $23$ 克金。{ 橡子，金，银，铜 }={ $0,23,0,0$ }
• 在交易所 $B$，用 $23$ 克金买 $46$ 个橡子。{ 橡子，金，银，铜 }={ $46,0,0,0$ }
• 在交易所 $A$，不做任何交易。{ 橡子，金，银，铜 }={ $46,0,0,0$ }

他不能得到 $47$ 个或更多橡子，因此答案是 $46$。