洛谷-P 1060楽しい金明

洛谷-P 1060楽しい金明
原題リンク:https://www.luogu.com.cn/problem/P1060

タイトル説明

入力フォーマット

出力フォーマット

入出力サンプル

説明/ヒント

C++コード

タイトルの説明
金明は今日とても楽しかったです.家で買った新しい家は鍵をもらいました.新しい家には自分専用の広い部屋があります.さらに彼を喜ばせたのは、お母さんが昨日彼に言ったことだ.「あなたの部屋にはどんなものを買う必要がありますか.どのように配置するか、あなたが決めてください.N元を超えなければいいです」.今日の朝、金明は予算を作り始めたが、彼が買いたいものが多すぎて、母の限定N元を超えるに違いない.そこで、彼は品物ごとに1つの重要度を規定して、5等に分けました:整数1−5で表して、5等が最も重要です.彼はまたインターネットからすべての品物の価格(すべて整数元)を調べた.彼はN元(N元に等しい)を超えない前提の下で、各品物の価格と重要度の積の総和を最大にすることを望んでいる.
j番目の物品の価格をv[j]、重要度をw[j]とし、k番目の物品を選択し、番号を(j_1,j_2,...,j_k)の順にすると、求めた総和は以下のようになる.
\(v[j_1]\times w[j_1]+v[j_2]\times w[j_2]+ …+v[j_k]\times w[j_k]\).
金明が要求を満たすショッピングリストを設計するのを手伝ってください.
入力フォーマット
1行目は、2つの正の整数で、1つのスペースで区切られています.n,m(ここで、N(<30000)は総金額を表し、m(<25)は購入したいものの個数です.)
2行目からm+1行目まで、j行目にはj−1と番号付けされた物品の基本データが与えられ、各行に2つの非負の整数vp(vは物品の価格((vle 10000))を表し、pは物品の重要度(1−5)を表す
出力フォーマット
1つの正の整数は、総金額を超えない物品の価格と重要度の積の総和の最大値(<1000000)である.
入出力サンプル
入力#1

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

出力#1

3900

説明/ヒント
NOIP 2006普及グループ第二題
C++コード

#include 
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))

int n,m,v[25],p[25],ans[30000];

int main() {
    cin>>n>>m;
    for(int i=0;i>v[i]>>p[i];
    for(int i=0;i=v[i];--j)
            ans[j]=max(ans[j],ans[j-v[i]]+v[i]*p[i]);
    cout<