题目描述

儿子的生日快到了，爸爸打算给儿子买生日礼物，他打算去商店挑选铅笔当作孩子的生日礼物。商店里有2种铅笔可供选择，不同的礼物价格可能不一样。由于爸爸只选同一种铅笔但是，商店又不允许拆分组合，所以爸爸只能在预算内买铅笔。现在爸爸想知道，在商店每种铅笔的数量都充足的情况下，要买够至少能满足需求的礼物，最少得花多少钱。

输入格式

第一行包含一个正整数$n$，表示需要买$n$支铅笔。 接下来两行，每行用$2$个正整数描述一种包装的铅笔:其中第1个整数表示这种包装内铅笔的数量，第2个整数表示这种铅笔的价格。 保证所有的7个数都是不超过 10000 的正整数。

输出格式

一个整数，表示爸爸最少需要花多少钱。

样例输入1

57
2 2
50 30

样例输出1

58

样例解释

爸爸需要购买至少 57支铅笔。 铅笔的三种包装分别是: 2 支装，价格为 2； 50 支装，价格为 30: 如果爸爸选择购买第一种包装，那么她需要购买 29份，共计2x29 =58支，需要花费的钱为2x29 =58. 如果选择第二种，这样需要买2份。虽然最后买到的铅笔数量更多了，为 30x2 = 60 支，但花费2x30=60，比第一种多。因此不会选择。 所以最后输出的答案是 58.

数据范围

对于全部数据，有 $1 \leq n \leq1000000000$ 。