题目描述

金明有 $N$ 元预算，想买 $m$ 件物品，每件最多购买一次。物品价格为 $v$，重要度为 $p$。在总价格不超过预算的情况下，使购买物品的价格与重要度乘积之和最大。

输入格式

第一行 $N,m$。接下来 $m$ 行，每行 $v,p$。

输出格式

输出最大的乘积之和。

样例

1000 5
800 2
400 5
300 5
400 3
200 2

3900

数据范围

$1\le N<30000$，$1\le m<25$，$1\le v<10000$，$1\le p\le5$。