题意描述

$\text{Cpg}$ 正在游览一个梦中之城，在这个城市中有$n$棵摇钱树。这下，可让$\text{Cpg}$看傻了。

$\text{Cpg}$只能在这个城市中呆$m$天，现在摇钱树已经成熟了，每天每棵都会掉下不同的金币。

$\text{Cpg}$每天可以砍掉其中一颗，并获得其树上所有的金币。

请你帮助$\text{Cpg}$算出他在这$m$天中最多能获得多少金币。

输入格式

每个文件中有不超过$10$组测试数据，对于每组测试数据，有：

第一行两个整数$n , m$

第二行$n$个整数$M_i$，表示$\text{Cpg}$刚看到这$n$棵树时树上的金币数。

第三行$n$个整数 $P_i$，表示每颗摇钱树每天将会掉落的金币。

以$n=m=0$结束。

输出格式

对每组测试数据，输出仅一行，表示$\text{Cpg}$在$m$天中能获得的最大金币数。

Input & Output ‘s examples

Input ‘s eg

3 3
10 20 30
4 5 6
4 3
20 30 40 50
2 7 6 5
0 0

Output ‘s eg

47
104

数据范围和约定

对于$100\%$的数据，有$1 < n < 1000$ ， $1 < m < 10^5$。

保证输入数据均在$\text{int}$范围内。

分析

先说方法：将每一棵树按照$p[i]$排序之后$01$背包。

贪心证明如下：

对于第$i$颗与第$i + 1$颗树，若分别在第$j$个与第$j + 1$个时刻被砍掉，则收益为 $m[i] - j \times p[i] + m[i + 1] - (j + 1) \times p[i + 1]$

如果交换一下砍树的顺序，则收益为 $m[i] - (j + 1) \times p[i] + m[i + 1] - j \times p[i + 1]$

显然，只有当后者的收益大于前者时才会交换。即 $m[i] - j \times p[i] + m[i + 1] - (j + 1) \times p[i + 1] < m[i] - (j + 1) \times p[i] + m[i + 1] - j \times p[i + 1]$

移一下项，就变成了$p[i] - p[i + 1] > 0$，即$p[i] > p[i + 1]$。

之后$01$背包即可，根据$01$背包的定义，可得状态转移方程 $f[i][j] = max(f[i - 1][j] , f[i - 1][j - 1] + max(0 , m[i] - p[i] \times (j - 1)))$

剩下的细节详见代码。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define clear(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

struct Node{
    int x , y;
}node[M];

bool cmp(Node a , Node b){
    return a.y > b.y;
}

int n , m;
int f[1001][1001];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    while(1){
        scanf("%d%d" , &n , &m);
        int ans = 0;
        if(n == 0 && m == 0) break;
        if(m > n) m = n;
        rep(i , 1 , n) scanf("%d" , &node[i].x);
        rep(i , 1 , n) scanf("%d" , &node[i].y);
        sort(node + 1 , node + 1 + n , cmp);
        rep(i , 1 , n){
            for(int j = m; j ; j --){
                f[i][j] = max(f[i - 1][j] , f[i - 1][j - 1] + max(0 , node[i].x - (node[i].y * (j - 1))));
            }
        }
        rep(i , 1 , m) ans = max(ans , f[n][i]);
        printf("%d\n" , ans);
    }

    return 0;
}