题目描述

PC 需要去雀玲珑买 $n$ 个炸鸡腿作为新生们每天刷题的奖励。他发现雀玲珑一共有 $3$ 种不同的炸鸡腿套餐，里面仅包含数个炸鸡腿，不同套餐之间只有炸鸡腿的数量和价格可能不同。为了方便，PC 决定只买 $1$ 种套餐。

在雀玲珑单独点一个炸鸡腿实在是太亏了，因此 PC 可能需要购买超过 $n$ 个炸鸡腿才够给新生们发奖励。

现在 PC 想知道，在雀玲珑每种套餐的数量都足够的情况下，要买够至少 $n$ 个炸鸡腿最少需要花费多少钱。

输入格式

第一行包含一个正整数 $n$ ，表示需要购买的炸鸡腿数量。

接下来三行，每行用 $2$ 个正整数 $m, k$ 描述一种套餐，表示该套餐内包含 $m$ 个炸鸡腿，套餐价格为 $k$。

输出格式

一个整数，表示 PC 最少需要花费的钱。

57
2 2
50 30
30 27

54

9998
128 233
128 2333
128 666

18407

9999
101 1111
1 9999
1111 9999

89991

提示

样例中雀玲珑的三种套餐分别是：

• $2$ 个炸鸡腿，价格为 $2$ 元。
• $50$ 个炸鸡腿，价格为 $30$ 元。
• $30$ 个炸鸡腿，价格为 $27$ 元。

PC 需要购买至少 $57$ 个炸鸡腿。

如果他选择购买第一种套餐，那么他需要购买 $29$ 份，共计 $2 \times 29 = 58$ 个炸鸡腿，需要花费的钱为 $2 \times 29 = 58$ 元。

实际上，PC 会选择购买第三种套餐，这样需要买 $2$ 份。虽然最后买到的炸鸡腿数量更多了，为 $30 \times 2 = 60$ 个，但花费却减少为 $27 \times 2 = 54$ 元，比第一种少。

对于第二种套餐，虽然单个炸鸡腿的价格是最低的，但要够发奖励必须购买 $2$ 份，实际的花费达到了 $30 \times 2 = 60$ 元，因此 PC 也不会选择。

所以最后输出的答案是 $54$。

现实中，雀玲珑一个套餐也不会有 $30000$ 个炸鸡腿，所以题目内容请勿带入现实，除非你想请我吃雀玲珑。

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m,k \leq 3 \times 10^4$。

本题改编自 NOIP 2016 普及组 T1