Overview

This is a problem where you select equipment such that the total defense is at least \(K\), and you want to maximize the total attack power. Since each piece of equipment can be selected at most once, this can be solved with the classic “0/1 Knapsack DP”.

Analysis

• The condition is not “total defense is exactly \(K\)” but rather “at least \(K\)”.
  However, we don’t need to distinguish values beyond \(K\) in detail — all we ultimately need is “whether the condition is achievable” and “the maximum attack power”.
• Naively trying all subsets would require \(2^N\) combinations, which is far too slow for \(N \le 100\).
• Instead, we use “total defense” as the state and manage the “maximum attack power” achievable for each state using DP.
• Although individual defense values can be up to \(10^4\) and their sum can be much larger, once the total exceeds \(K\), we treat it all as \(K\) (capping it), which keeps the number of states to \(K+1\).

Example: When \(K=10\), defense totals of \(10, 11, 100\) are all the same in terms of “satisfying the entry condition”, so they are all merged into state \(10\).

Algorithm

Define the DP array as follows:

• \(dp[w]\): the maximum total attack power achievable when the total defense is \(w\) (where \(w\) ranges from \(0\) to \(K\), and \(K\) represents “\(K\) or more”)
• Unreachable states are represented by a very small value (\(-\infty\))

Initialization: - \(dp[0]=0\) (selecting nothing) - All others are \(-\infty\)

For each piece of equipment \((W_i, S_i)\), since it is 0/1 (at most once), we update from back to front: - Adding equipment from current state \(w\) gives a new defense of \(nw = \min(K, w + W_i)\) - The attack power becomes \(dp[w] + S_i\) - Update if a greater attack power is obtained

Finally: - If \(dp[K]\) is \(-\infty\), there is no valid selection that satisfies the condition, so output -1 - Otherwise, \(dp[K]\) is the answer

Complexity

• Time complexity: \(O(NK)\)
  (For each piece of equipment, we update \(w=0\sim K\))
• Space complexity: \(O(K)\)
  (Only a single DP array)

Implementation Notes

• Looping from back to front (for w in range(K, -1, -1)) prevents the same piece of equipment from being used multiple times within a single iteration (a fundamental technique of 0/1 knapsack).

• When \(w+W_i\) exceeds \(K\), we clamp it to K (capping), which correctly handles the “at least \(K\)” condition.

• For unreachable state detection, we use a sufficiently small value such as NEG = -10**18, and we do not transition from states where dp[w] == NEG.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    NEG = -10**18
    dp = [NEG] * (K + 1)
    dp[0] = 0

    for w_i, s_i in items:
        for w in range(K, -1, -1):
            if dp[w] == NEG:
                continue
            nw = w + w_i
            if nw > K:
                nw = K
            val = dp[w] + s_i
            if val > dp[nw]:
                dp[nw] = val

    print(dp[K] if dp[K] != NEG else -1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.