注文する料理の組み合わせは \(2 ^ N\) 通りあります。 この問題の制約のもと、これはたかだか \(524288\) 通りと小さいので、それらの組み合わせすべてに対して満足度を計算することができます。

時間計算量は \(O(N2 ^ N)\) などになります。

実装例は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    int N, K, D;
    cin >> N >> K >> D;
    vector<pair<int, int>> menu(N);
    for (auto& [A, B] : menu) {
        cin >> A >> B;
    }

    long ans = 0;
    for (int bit = 0; bit < 1 << N; ++bit) { // すべての選び方に対して
        long A_sum = 0, B_sum = 0;
        for (int i = 0; i < N; ++i) { // それぞれの料理が
            if (bit >> i & 1) { // 含まれるなら
                A_sum += menu[i].first; // おいしさと
                B_sum += menu[i].second; // こってり度を足す
            }
        }
        ans = max(ans, A_sum - D * (max<long>(K, B_sum) - K)); // 満足度を計算して、最大値を求める
    }

    cout << ans << endl;
    return 0;
}

N, K, D = map(int, input().split())

menu = [tuple(map(int, input().split())) for _ in range(N)]

ans = 0
for bit in range(1 << N): # すべての選び方に対して
    A_sum = 0
    B_sum = 0
    for i in range(N): # それぞれの料理が
        if bit >> i & 1: # 含まれるなら
            A_sum += menu[i][0] # おいしさと
            B_sum += menu[i][1] # こってり度を足す
    ans = max(ans, A_sum - D * max(0, B_sum - K)) # 満足度を計算して、最大値を求める

print(ans)