题目描述

P老师需要去商店买 n 支铅笔作为小朋友们参加NOIP的礼物。商店一共有3种包装的铅笔，不同包装内的铅笔数量和价格可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。

商店不允许拆开包装，因此P老师可能需要购买超过 n 支铅笔才能满足需求。现在需要计算：在每种包装数量足够的情况下，购买至少 n 支铅笔所需花费的最少金额。

输入格式

• 第一行：一个正整数 n，表示需要的铅笔数量。
• 接下来三行：每行两个正整数，分别表示一种包装的铅笔数量 a_i 和价格 b_i。

数据保证：所有输入的正整数不超过 10000。

输出格式

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

样例

输入 #1

57
2 2
50 30
30 27

输出 #1

54

解释：

• 第一种包装：需买 29 份（共 58 支），花费 58 元。
• 第二种包装：需买 2 份（共 100 支），花费 60 元。
• 第三种包装：需买 2 份（共 60 支），花费 54 元。
  最优解为第三种包装，输出 54。

输入 #2

9998
128 233
128 2333
128 666

输出 #2

18407

输入 #3

9999
101 1111
1 9999
1111 9999

输出 #3

89991

数据范围与提示

• 数据范围：所有整数 1 ≤ n, a_i, b_i ≤ 10000。