程序设计能力实训

1041. 闪卡销售

单点时限: 1.0 sec

内存限制: 256 MB

公司有 种类型的闪卡要出售,闪卡类型编号为 ,第 种类型的闪卡数量为

现有多个收购商给出的 条关于闪卡的报价信息 ,表示收购第 种类型的闪卡的单价为

请计算公司如何销售,才能获得最多收益。

每个收购商可以收购无限量的闪卡。

输入格式

第一行输入两个整数 (),其中 为闪卡类型数目, 为报价信息数目。

第二行输入 个整数 () 表示第 种类型闪卡数量。

接下来 行,每行输入两个整数 (),表示第 种类型的闪卡的报价

输出格式

输出一行,即最多卖出多少价值的闪卡。

样例

Input
2 6
1 2
1 2
1 3
1 4
2 1
2 3
1 7
Output
13
不限期开放

题目列表