背景

方块鸟第一次月赛结束啦，只要在比赛中成功AC一个题目的参赛者，都将获得参赛纪念品。网上售卖的纪念品都是成组出售的，不能单买（其实也不是不可以，就是单买贵一些嘛 🤫 ） 在我们的第一次月赛中，共有$14$个同学成功AC了一道题目，黄老师在网上找到了三种不同的纪念品：

为了公平，给大家的纪念品肯定都要一样的，黄老师简单的算了一下购买这三种分别需要多少钱，过程如下：

水壶一共要买5组（15个），共计50元 卡包一共要买3组（15个），共计42元 胸针一共要买2组（20个），共计200元

算下来，买3组卡包是够给14位同学发奖品并且总价最低的。

你要做的就是编写一个程序，针对不同的纪念品数量$n$和商品组合，算出准备足够纪念品的最低价格。

输入输出格式

输入

四行。 第一行为一个正整数$n$，需要准备的纪念品数量。 随后三行，每行两个正整数$a, p$，以空格分割。其中$a$为某纪念品每组的数量，$p$为某纪念品每组的价格。

输出

一行，购买足够纪念品的最低价格。

样例

14
3 10
5 14
10 100

42

限制

题目中的7个数字都不会超过$10,000$。