Overview

Given \(N\) pieces of equipment, select some of them so that the total defense is at least \(K\), and maximize the total attack power.

Analysis

This problem is a variation of the classic “knapsack problem.” In the standard knapsack problem, there is a constraint like “the sum of weights is at most ~”, but here we have a lower bound constraint: “the sum of defense must be at least \(K\).”

A brute-force search over all \(2^N\) subsets is not feasible when \(N=100\) since \(2^{100}\) is astronomically large. Greedy approaches are also difficult to apply — for example, a strategy like “select equipment in decreasing order of attack power” may fail to satisfy the defense condition, and thus may not yield the optimal solution.

Therefore, we consider using dynamic programming (DP). We define the DP table as follows:

\(dp[w] :=\) the maximum attack power obtainable among all selections where the total defense is exactly \(w\)

However, since we only need the defense to be at least \(K\), we can merge all states where \(w \geq K\) into \(w = K\), avoiding unnecessary computation. This means the DP table size is at most around \(K\).

The updates correspond to the “select” or “don’t select” decision for each piece of equipment. Similar to the standard knapsack, by updating from the back (in reverse order), we naturally ensure each item is used at most once.

Finally, the answer is the maximum value among \(dp[K]\) and beyond. If all values are -1 (unreachable), then no valid selection exists, so we output -1.

Algorithm

This problem can be solved with a “knapsack-style DP that maximizes an evaluation value (attack power) based on subset sums.”

DP Definition:

• dp[w]: the maximum attack power when selecting equipment such that the total defense is exactly \(w\) (or -1 if unreachable)

For \(w \geq K\), all states are merged into \(w = K\) (since making the defense any larger serves no purpose).

Update Method:

For each piece of equipment \((W_i, S_i)\), iterate \(w\) from large to small:

• If dp[w] != -1, then
• For the new state new_w = min(w + W_i, K),
• Update dp[new_w] = max(dp[new_w], dp[w] + S_i)

This ensures each item is used at most once while finding the maximum attack power.

Final Answer:

The maximum value among \(dp[K]\) and beyond is the answer. If all are -1, output -1.

Complexity

• Time complexity: \(O(N \cdot K)\)
• Space complexity: \(O(K)\)

Since \(N \leq 100\) and \(K \leq 10^4\), this is sufficiently fast.

Implementation Notes

• The DP table size of min(sum(W), K)+1 is sufficient (there is no need to exceed the upper bound of defense)

• To ensure each item is used at most once, the inner loop must iterate in reverse order

• When w >= K, merge everything into K (cap the index using min(..., K))

• Initialize with dp[0] = 0 and all others as -1 (unreached)

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    W = []
    S = []
    index = 2
    for _ in range(N):
        w = int(data[index])
        s = int(data[index+1])
        W.append(w)
        S.append(s)
        index += 2
    
    # dp[i][w] := i番目まで見て、防御力がちょうどwとなるときの最大攻撃力
    # ただし、w >= K についてはまとめて w = K として扱う
    max_w = min(sum(W), K)
    dp = [-1] * (max_w + 1)
    dp[0] = 0
    
    for i in range(N):
        w = W[i]
        s = S[i]
        # 逆順に更新することで、各アイテムを一度だけ使う制約を満たす
        for j in range(max_w, -1, -1):
            if dp[j] == -1:
                continue
            new_w = min(j + w, max_w)
            new_s = dp[j] + s
            if dp[new_w] < new_s:
                dp[new_w] = new_s
    
    result = -1
    for i in range(K, max_w + 1):
        if dp[i] > result:
            result = dp[i]
    
    print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.