#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

ll n,d;
pair<pair<ll,ll>,ll> a[1005];
ll dp[1005][1005];

int main()
{
    cin >> n >> d;
    for (int i=1;i<=n;i++){
        cin >> a[i].fi.fi;
        a[i].se = i;
    }
    for (int i=1;i<=n;i++){
        cin >> a[i].fi.se;
    }
    sort(a+1, a+1+n);
    memset(dp, 0LL, sizeof dp);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if (j >= d && j <= a[i].fi.fi){
                dp[i][j] = max(dp[i][j], dp[i-1][j-d] + a[i].fi.se);
            }
        }
    }
    ll ans = dp[n][n];
    cout << ans << '\n';
    ll i = n, j = n;
    vector<ll> res;
    while (i > 0 && j > 0){
        if (dp[i][j] == dp[i][j-1]) j--;
        else if (dp[i][j] == dp[i-1][j]) i--;
        else {
            res.push_back(a[i].se);
            ll tmp = 0;
            for (int x=1;x<=j;x++){
                if (dp[i][j] - a[i].fi.se == dp[i-1][x]){
                    tmp = x;
                }
            }
            j = tmp;
            i--;
        }
    }
    reverse(res.begin(), res.end());
    for (auto it:res) cout << it << " ";
    return 0;
}

giải thích:

Sử dụng quy hoạch động:

- Giả sử, t[a] <= t[b] nếu chọn xem nghệ sĩ b sau đó xem nghệ sĩ a thì cũng tương tự như việc xem nghệ sĩ a sau đó xem nghệ sĩ b. Vì vậy chúng ta có thể sắp xếp mảng tăng dần theo thời gian kết thúc mà không ảnh hưởng đến kết quả của bài toán.

- Gọi dp[i][j] là tổng giá trị lớn nhất khi xét i nhóm nghệ sĩ đầu tiên với thời gian là j. 

- dp[i][j] = max(

                 dp[i-1][j] (không chọn xem nghệ sĩ i)

                 dp[i][j-1] (xem nghệ sĩ i với thời gian trước đó)

                 dp[i-1][j-d] + a[i].second (xem nghệ sĩ i và những nghệ sĩ xem tối ưu với thời gian j-d, thời gian j-d là vì khi xét đến j thì đủ thời gian để nhận quà khuyến mại).

- Đáp án sẽ là dp[n][n].