P16289
// 若电池容量为0，显然只能现买现用
// 若电池容量无限大，显然每次都用前缀最小值来买
// 那么当电池容量为k时，电池中的电量应当存储价格最便宜的k个单位（每个单位电量对应的c[i]越小越好）
// 考虑用set动态维护这k个单位的电量
// 每来到一个新的任务 (c[i], w[i]) 时：
// 1. 首先需要在这里购买电量（暂时存到电池中，容量超过k也无所谓；为了覆盖到所有情况，最多需要买 k + w[i] 单位电量(即此时c[i]特别小，需要先完成现在的消耗任务，再用最多k个单位电量补满电池)）
// 2. 然后贪心地用当前电池里最便宜的 w[i] 个单位电量去完成当前消耗电量任务；
// 3. 完成后电池容量可能会超过k，为了让总花费最小，显然我们应当贪心地删除 set 里面最贵的电量，直到电池内总电量剩余恰好k个单位
// 然后执行后续任务，并按照上述过程继续贪心
// 复杂度分析：每次来到一个任务，set 只会添加一个 (c[i], k + w[i])，即恰好添加 n 个元素
// 而在进行购买电量引起的删除操作时，只会在删除若干个元素后，最多进行一次额外插入（相当于修改最后一个被删除的元素）
// 处理超过容量的电池电量时也是同理
// 因此总插入次数不超过 3n（每次执行任务最多进行3次插入操作），删除也只会从这 3n 个插入的元素中删
// 故总复杂度 O(nlogn)
void solve()
{int n, k;cin >> n >> k;vector<int> w(n + 1), c(n + 1);LL res = 0;for(int i = 1; i <= n; i ++){cin >> w[i];}for(int i = 1; i <= n; i ++){cin >> c[i];res += 1ll * w[i] * c[i];}if(k == 0){print(res);return;}LL ans = 0;LL sum = 0; // 当前 set 内的总电量有多少单位multiset<pair<int,LL>> ms; // {电池单位价格，电池容量大小}for(int i = 1; i <= n; i ++){// 先购买 k + w[i] 个单位当前电池电量ms.insert({c[i], k + w[i]});sum += k + w[i];// 用当前 set 里最便宜的 w[i] 个单位电量去完成当前的消耗电量任务int now = w[i];while(1){assert(!ms.empty());auto [cost, rest] = *ms.begin();if(rest >= now){ans += 1ll * cost * now;ms.erase(ms.begin());if(rest > now) ms.insert({cost, rest - now});sum -= now;now = 0;break;}else{ans += 1ll * cost * rest;now -= rest;sum -= rest;ms.erase(ms.begin());}} assert(now == 0);// 删除容量超过k的部分，直到电池内剩余k个最便宜的单位电量while(1){assert(!ms.empty());auto [cost, rest] = *(--ms.end());if(rest >= sum - k){ms.erase(--ms.end());if(rest > sum - k) ms.insert({cost, rest - (sum - k)});sum = k;break;}else{sum -= rest;ms.erase(--ms.end());}}assert(sum == k);}print(ans);
}
