全ての缶詰に缶切りが必要ない場合を考えると、安い缶詰から順に \(M\) 個買うのが最適です。
缶切りが必要な場合でも、買う缶切りの個数や缶切りが必要な缶詰を買う個数を固定すれば、同様に貪欲法を適用することができます。
そのため、以下のように解くことができます。

• \(T_i = 0\) の缶詰の値段を昇順ソートしたものを \(A_1, A_2, \dots, A_n\) とする。
• \(T_i = 1\) の缶詰の値段を昇順ソートしたものを \(B_1, B_2, \dots, B_{N-n}\) とする。
• \(i = \max(0,M-n), \dots, \min(M,N-n)\) について、缶切りが必要な缶詰を \(i\) 個買う場合の合計金額 \(S_i\) を求める。
  \(\displaystyle S_i = \sum_{1≤x≤M-i}A_x + \sum_{1≤x≤i}B_x + Q\left\lceil\frac iK\right\rceil\) である。
• \(S_{i+1} - S_i\) は \(O(1)\) で計算できる。\(\underset{i}{\min} S_i\) が答えである。

回答例 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
void chmin(ll& a, ll b){ if(a > b) a = b; }

int main(){
    ll N, M, K, Q;
    cin >> N >> M >> K >> Q;
    vector<ll> A, B;
    while(N--){
        ll P, T;
        cin >> P >> T;
        (T ? B : A).push_back(P);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    A.push_back(0);
    exclusive_scan(A.begin(), A.end(), A.begin(), 0LL);
    B.push_back(0);
    exclusive_scan(B.begin(), B.end(), B.begin(), 0LL);
    ll ans = 1LL << 60;
    for(ll i = 0; i < B.size(); i++){
        const ll j = M - i;
        if(0 <= j && j < A.size()) chmin(ans, A[j] + B[i] + (i + K - 1) / K * Q);
    }
    cout << ans << endl;
}

回答例 (Python)

N, M, K, Q = map(int, input().split())
A = []
B = []
for i in range(N):
    P, T = map(int, input().split())
    if T == 0:
        A.append(P)
    else:
        B.append(P)

A.sort()
B.sort()
A.insert(0, 0)
for i in range(len(A) - 1):
    A[i + 1] += A[i]
B.insert(0, 0)
for i in range(len(B) - 1):
    B[i + 1] += B[i]

ans = 1 << 60
for i in range(len(B)):
    j = M - i
    if 0 <= j < len(A):
        ans = min(ans, A[j] + B[i] + (i + K - 1) // K * Q)

print(ans)