def thief_knapsack(weights, values, M, K):
    cap = M * K
    n = len(weights)
    dp = [0] * (cap + 1)
    take = [[False] * (cap + 1) for _ in range(n)]
    for i in range(n):
        w = weights[i]
        v = values[i]
        for c in range(cap, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
                take[i][c] = True
    c = cap
    items = []
    for i in range(n - 1, -1, -1):
        if take[i][c]:
            items.append(i)
            c -= weights[i]
    items.reverse()
    return dp[cap], items


if __name__ == "__main__":
    weights = [2, 3, 4, 5, 9, 7, 3]
    values = [3, 4, 5, 8, 10, 7, 6]
    M = 2
    K = 10
    best, items = thief_knapsack(weights, values, M, K)
    print(best, items)