#1077. 1-11B. JM的招摇撞骗

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

JM不仅经营黑心商店,还会在月黑风高的夜晚,打扮成一个派大星,出门到处骗人。今天晚上jwp和zzy在搬运浓芙膻泉,很不巧地遇到了派大星。派大星告诉他们,要想成为像cyy那么强的dalao,就必须虔诚地供奉咕呐啦执杖之神,获得无上神力庇佑,就能吊打cyy。

虽然jwp和zzy本来就是dalao,但他们仍然被骗了(?)。JM告诉他们,只要把两块五毛八一斤的浓芙膻泉交给他,他就可以帮两人将其献给咕咕咕……哦不,献给咕呐啦执杖之神。JM带了一个水桶,容积为 升。jwp和zzy搬着一箱子共 瓶不同品种的浓芙膻泉,第 瓶装了 升,且每升的价值为

为了尽可能打动咕呐啦执杖之神,jwp和zzy决定尽可能地献出价值更高的浓芙膻泉。而浓芙膻泉是一种神奇的东西,即使不同种类的浓芙膻泉混合在一起也没关系,所以他们只需要往水桶里灌到满就好了。他们想知道他们最多能献出价值多高的浓芙膻泉。

输入格式

第一行两个正整数

接下来 行,每行两个正整数

输出格式

输出一行一个正整数表示答案。

样例

样例输入1

100 2
70 5
80 3

样例输出1

440

样例输入2

100 2
40 1
50 1

样例输出2

90

数据范围与提示