题目描述

商店里有 $3$ 种铅笔出售。

• 第一种：每包有 $a_1$ 支，售价 $b_1$ 元；
• 第二种：每包有 $a_2$ 支，售价 $b_2$ 元；
• 第三种：每包有 $a_3$ 支，售价 $b_3$ 元。

所有铅笔只能整包买，不能拆开。

求：买至少 $n$ 支铅笔的总费用的最小值。

输入格式

第 $1$ 行：一个整数 $n$，表示购买的数量。

第 $2 \sim 4$ 行：每行两个整数 $a_i,b_i$，分别表示每种铅笔每包的数量和价格。

输出格式

一个整数，表示买至少 $n$ 支铅笔的费用的最小值。

样例

10
3 15
6 27
2 12

51

12
7 10
4 7
6 11

20

样例 $1$ 解释

第二种铅笔买 $1$ 包，第三种铅笔买 $2$ 包，总共买了 $101$ 支，花费 $51$ 元，是费用最少的方案。

样例 $2$ 解释

第一种铅笔买 $2$ 包，总共买了 $14$ 支，花费 $20$ 元，是费用最少的方案。

数据规模与约束

对于 $50\%$ 的测试点，保证所有 $a_i$ 都可以整除 $n$；

对于 $100\%$ 的测试点，保证 $1≤n,a_i,b_i≤100$。