この問題は、ナップサック DP に「直前の要素を選んだか」の場合分けを加えることで解くことができます。

具体的には、\(\mathrm{dp} _ i[j]\coloneqq\) 街路灯 \(i\) までを交換費用が \(j\) 円以下になるように交換するときの電気代削減効果の最大値 として、

\[\mathrm{dp} _ i[j]=\begin{cases}0&(i\le0\vee j\le 0)\\\max\lbrace\mathrm{dp} _ {i-1}[j],\mathrm{dp} _ {i-2}[j-W _ i]+V _ i\rbrace&(\textrm{otherwise})\end{cases}\]

と計算することができます（一つ目は街路灯 \(i\) を交換しない場合、二つ目は交換する場合に対応します）。

これを実装することで、\(O(NK)\) 時間でこの問題を解くことができます。 DP テーブルを使いまわすことで空間計算量を \(O(NK)\) から \(O(K)\) にすることもできます。

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<long> dp(K + 1), prev(K + 1);
    for (int i = 0; i < N; ++i) {
        int V, W;
        cin >> V >> W;
        swap(dp, prev);
        // 交換する場合
        for (int j = K - W; j >= 0; --j) {
            dp[j + W] = max(dp[j + W], dp[j] + V);
        }
        // 交換しない場合
        for (int j = 0; j <= K; ++j) {
            dp[j] = max(dp[j], prev[j]);
        }
    }

    cout << dp[K] << endl;
    return 0;
}

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

dp = [0 for i in range(K + 1)]
prev = [0 for i in range(K + 1)]

for i in range(N):
    V, W = map(int, input().split())
    dp, prev = prev, dp

    # 交換する場合
    for j in range(K - W, -1, -1):
        dp[j + W] = max(dp[j + W], dp[j] + V)

    # 交換しない場合
    for j in range(K + 1):
        dp[j] = max(dp[j], prev[j])

print(dp[K])