rqnoj/2.c

   1 #include <stdio.h>
   2
   3 #define max_value 50010
   4 #define maxn 25
   5
   6 int max(int p, int q) {
   7         return p>q?p:q;
   8 }
   9
  10 int main() {
  11         int money,n;
  12         scanf("%d%d",&money,&n);
  13         int f[max_value]={0},value[maxn],price[maxn];
  14         int i,j;
  15         for (i=1; i<=n; i++) scanf("%d%d",&(price[i]),&value[i]),value[i]*=price[i];
  16         for (i=1; i<=n; i++)
  17                 for (j=money; j>=price[i]; j--)
  18                         f[j]=max(f[j],f[j-price[i]]+value[i]);
  19         int ans=0;
  20         for (i=0; i<=money; i++) ans=max(ans,f[i]);
  21         printf("%d\n",ans);
  22         return 0;
  23 }