PRoblem Description

王小二畢業(yè)后從事船運規(guī)劃工作，吉祥號貨輪的最大載重量為M噸，有10種貨物可以裝船。第i種貨物有wi噸，總價值是pi。王小二的任務是從10種貨物中挑選若干噸上船，在滿足貨物總重量小于等于M的前提下，運走的貨物的價重比最大。

Input

輸入數(shù)據(jù)的第一行有一個正整數(shù)M(0 < M < 10000)，表示所有貨物最大載重量。在接下來的10行中，每行有若干個數(shù)（中間用空格分開），第i行表示的是第i種貨物的貨物的總價值pi ,總重量wi。(pi是wi的整數(shù)倍，0 < pi , wi < 1000)

Output

輸出一個整數(shù)，表示可以得到的最大價值。

Example Input

10010 1020 1030 1040 1050 1060 1070 1080 1090 10100 10
Example Output
550
Hint
價重比：計算其價值與重量之比
C++
#include<stdio.h>#include<algorithm>    using namespace std;    struct node    {      int p;      int w;      int bi;    }size[10];    int cmp(node a,node b)    {      return a.bi>b.bi;    }    int main()    {      int m,i,sum,flag;      scanf("%d",&m);         sum=0;flag=0;         for(i=0;i<10;i++)         {            scanf("%d%d",&size[i].p,&size[i].w);            size[i].bi=size[i].p/size[i].w;         }         sort(size,size+10,cmp);        for(i=0;i<10;i++)        {            if(flag<m)            {                sum+=size[i].p;                flag+=size[i].w;            }            else if(flag==m)            {                break;            }            else            {                flag=flag-size[i-1].w;                sum=sum-size[i-1].p;                sum=sum+(m-flag)*size[i-1].bi;                break;            }        }        printf("%d/n",sum);       return 0;    }
   C
#include<stdio.h>struct node{      int p;      int w;      int bi;}size[10],t;int main(){    int m,sum,flag,i,j;    scanf("%d",&m);        sum=0;        flag=0;        for(i=0;i<10;i++)        {            scanf("%d %d",&size[i].p,&size[i].w);            size[i].bi=size[i].p/size[i].w;        }        for(i=0;i<10;i++)        {            for(j=0;j<9-i;j++)            {                if(size[j].bi<size[j+1].bi)                {                    t=size[j],size[j]=size[j+1],size[j+1]=t;                }            }        }        for(i=0;i<10;i++)        {            if(flag<m)            {                sum+=size[i].p;                flag+=size[i].w;            }            else if(flag==m)            {                break;            }            else            {                flag=flag-size[i-1].w;                sum=sum-size[i-1].p;                sum=sum+(m-flag)*size[i-1].bi;                break;            }        }            printf("%d/n",sum);    return 0;}