http://acm.hdu.edu.cn/showproblem.php?pid=2670
//1311986 2009-04-26 19:58:30 Accepted 2670 78MS 4180K 934 B C++ no way 
#include<iostream>
#include
<algorithm>
#define MAX(x,y) x>y?x:y
using namespace std;
struct node
{
    
int love;
    
int dece;
}
;
bool comp(node a,node b)
{
    
return a.dece > b.dece;
}

int dp[1001][1001];//dp[i][j] 表示前i个人中选j个的最优值
int lvs[1001][1001];
int main()
{
    
int n,k;
    
while(scanf("%d%d",&n,&k)!=EOF)
    
{
        
int i,j,maxs;
        node infor[
1001];
        
for(i=1;i<=n;i++)
            scanf(
"%d",&infor[i].love);
        
for(i=1;i<=n;i++)
            scanf(
"%d",&infor[i].dece);
        sort(infor
+1,infor+n+1,comp);
        
////////////////////////////////////////////////////////////////
        for(i=1;i<=n;i++)
            
for(j=1;j<=k;j++)
                lvs[i][j] 
= infor[i].love - (j-1)*infor[i].dece;
        
//这样处理时间并未节约,相反还浪费了空间~????
        ////////////////////////////////////////////////////////////////
        maxs = 0;
        
for(i=1;i<=n;i++)
        
{
            
if(infor[i].love > maxs)
                maxs 
= infor[i].love;
            dp[i][
1= maxs;
        }

        
for(i=2;i<=n;i++)
        
{
            
for(j=2;j<=&& j<=i;j++)
            
{
                
if(i-1>=j)
                    dp[i][j] 
= MAX(dp[i-1][j],dp[i-1][j-1+ lvs[i][j]);
                
else
                    dp[i][j] 
= dp[i-1][j-1+ lvs[i][j];
            }

        }

        cout
<<dp[n][k]<<endl;
    }

    
return 0;
}