A281.小伟的购物计划

小伟家购置了新房子，有了他自己的房间，他需要购买一些物品。妈妈对他说：“你的房间需要购买什么物品，怎么布置，你说了算，但不超过 $N$ 元钱”。小伟开始做预算，可他想买的东西太多了，若全买肯定会超过妈妈限定的预算 $N$ 元。于是他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1−5$ 表示，第 $5$ 等最重要。
他还查到了每件物品的价格（都是整数）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 $j$ 件物品的价格为 $v[j]$，重要度为 $w[j]$，共选中了 $k$ 件物品，编号依次为 j₁,j₂,…,j_k，则所求的总和为：

v[j₁]×w[j₁]+v[j₂]×w[j₂]+.......+v[j_k]×w[j_k]

请你帮助小伟设计一个满足要求的购物单。

第一行，为 $2$ 个正整数，用一个空格隔开：$n$ $m$（其中$n<30000$)表示总钱数，$m<25$为希望购买物品的个数。)
从第$2$行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j−1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v$ $p$ (其中 $v$ 表示该物品的价格($v≤10000$)，$p$ 表示该物品的重要度($1−5$)

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值($<100000000$)。