题目描述

金明想购买若干物品，总预算为 $N$ 元。共有 $m$ 件候选物品，第 $j$ 件物品价格为 $v_j$，重要度为 $w_j$（$1sim5$）。若购买一件物品，它对金明的价值为 $v_j imes w_j$。

请在总价格不超过 $N$ 的前提下，选择若干件物品，使所选物品价值总和最大。

输入格式

第一行输入两个正整数 $N,m$，分别表示总预算和物品数。 接下来 $m$ 行，每行输入两个正整数 $v,w$，表示一件物品的价格和重要度。

输出格式

输出一行一个整数，表示可获得的最大价值总和。

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

3900

数据范围与提示

• $N<30000$，$m<25$。
• $v \le 10000$，$1 \le w\le 5$。
• 样例中选择第 $2,3,5$ 件物品，总价格 $900 \le 1000$，总价值 $3900$。

来源

NOIP 2006 普及组 / 开心的金明