Overview

Among the ways to select products within a budget of \(K\), we want to find the maximum total price (the value closest to \(K\)). This is a classic “subset sum” problem, where we manage the reachable total amounts using DP.

Analysis

Key Insight

The condition “select some products” means each product has two choices: select or not select. So we just need to track “which total values can be achieved.” In other words, if we can determine “Can a total of \(s\) yen be achieved?” for the range \(s=0..K\), then we search downward from \(K\) to find the maximum reachable value as the answer.

Why Naive Approaches Don’t Work

• Brute force: There are \(2^N\) ways to select products, which is far too many when \(N \le 100\).
• Standard DP (using an array \(dp[s]\)): \(O(NK)\), which is about \(100 \times 10^4 = 10^6\) in this case and is fast enough. However, in Python there is an even faster way to implement this.

How to Solve It

We represent the set of reachable totals \(s\) as a bit string. - Bit \(s\) of bits is 1 ⇔ a total of \(s\) can be achieved - When adding a product with price \(c\), the reachable set is updated as bits | (bits << c) (Because “adding \(c\) to every currently achievable total” can be expressed as a left shift)

This method can be processed efficiently using Python’s arbitrary-precision integer bit operations.

Algorithm

1. Set bits = 1 (since a total of \(0\) yen is always achievable, set bit 0 to 1).
2. For each product price \(c\):
   • If \(c > K\), it cannot contribute to any total within the budget, so skip it.
   • Update the reachable totals with bits |= (bits << c).
   • However, bits exceeding \(K\) are unnecessary, so trim to the range \(0..K\) using mask = (1 << (K+1)) - 1 and bits &= mask.
3. Finally, the highest set bit position in bits is the answer.
   • bits.bit_length() - 1 returns “the position of the most significant 1-bit,” which gives the maximum reachable total (since it’s already masked, it is guaranteed to be \(\le K\)).

Concrete Example

When \(K=7\) and products are \([3,5]\): - Initial: bits represents only total 0 as achievable → ...0001 - \(c=3\): - bits<<3 represents total 3 as achievable → ...1000 - After OR, totals 0 and 3 are achievable → ...1001 - \(c=5\): - bits<<5 represents totals 5 and 8 as achievable, but \(8\) is unnecessary (removed by mask) - After OR, totals 0, 3, and 5 are achievable → maximum is 5

Complexity

• Time complexity: approximately \(O\!\left(N \cdot \frac{K}{w}\right)\) (\(w\) is the machine word size. Bit operations process “\(K\) bits worth” at once, making it fast)
• Space complexity: \(O(K)\) (storing \(K+1\) bits of information)

Implementation Notes

• It is important to use mask = (1 << (K + 1)) - 1 to keep only bits \(0..K\) (without this, bits keeps growing larger and becomes slow).

• Products with \(c > K\) can be skipped since they cannot be used in any total within the budget.

• The answer can be obtained with bits.bit_length() - 1 (since it’s already masked, it is guaranteed to be at most \(K\)).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    C = data[2:2+N]

    bits = 1  # sum 0 is possible
    mask = (1 << (K + 1)) - 1
    for c in C:
        if c <= K:
            bits |= (bits << c)
            bits &= mask

    print(bits.bit_length() - 1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.