總分 Score Inflation-洛谷 2722

題目背景

學生在我們USACO的競賽中的得分越多我們越高興。

我們試着設計我們的競賽以便人們能盡可能的多得分,這需要你的幫助

題目描述

我們可以從幾個種類中選取競賽的題目,這裡的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間并且能得到相同的分數。你的任務是寫一個程式來告訴USACO的職員,應該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規定的時間裡并且總分最大。輸入包括競賽的時間,M( <= M <= ,)(不要擔心,你要到了訓練營中才會有長時間的比賽)和N,"種類"的數目 <= N <= ,。後面的每一行将包括兩個整數來描述一個"種類":

第一個整數說明解決這種題目能得的分數( <= points <= ),第二整數說明解決這種題目所需的時間( <= minutes <= )。

你的程式應該确定我們應該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分數。

來自任意的"種類"的題目數目可能是任何非負數(或更多)。

計算可能得到的最大分數。

輸入輸出格式

輸入格式：
第  行: M, N--競賽的時間和題目"種類"的數目。

第 -N+ 行: 兩個整數:每個"種類"題目的分數和耗時。

輸出格式：
單獨的一行包括那個在給定的限制裡可能得到的最大的分數。

輸入輸出樣例

輸入樣例#：
 
 
 
 
 
輸出樣例#：


題解：這道題很明顯是一道完全背包。

源代碼：
var
  f:array[] of longint;
  n,m,i,j,x,y:longint;
begin
  readln(m,n);
  for i:= to n do
   begin
     readln(y,x);
     for j:=x to m do
      if f[j-x]+y>f[j] then f[j]:=f[j-x]+y;
   end;
  writeln(f[m]);
end.