#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int love;
int bb;
}Node;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Node a[1005];
int dp[1005][1005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool cmp(Node a,Node b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return a.bb > b.bb;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int getMax(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(a > b)
return a;
else
return b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,k;
while(scanf("%d%d",&n,&k) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j;
for(i = 1; i <= n;i++)
scanf("%d",&a[i].love);
for(i = 1;i <= n;i++)
scanf("%d",&a[i].bb);
sort(a+1,a+n+1,cmp);
int maxs = 0;
for(i = 1;i <= n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(maxs < a[i].love)
maxs = a[i].love;
dp[i][1] = maxs;
}
for(i = 1;i <= n;i++)
for(j = 2;j <= i && j <= k; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][j] = getMax(dp[i-1][j],dp[i-1][j-1] + a[i].love - (j-1)*a[i].bb);
}
printf("%d\n",dp[n][k]);
}
return 0;
}