Overview

Each chemical has 3 choices: “don’t use / normal mode / heated mode”, so an exhaustive search would require \(3^N\) combinations.
Checking all of them directly is too large, so we use Meet-in-the-Middle to reduce it to approximately \(3^{N/2}\) and then perform the check.

Analysis

For each chemical, the choices are the following three:

• Don’t use (\(+0\))
• Normal mode (\(+A_i\))
• Heated mode (\(+B_i\))

Therefore, a naive exhaustive search has \(3^N\) states.
With a maximum of \(N=26\), \(3^{26}\) is extremely large and cannot be processed in a realistic time.

The key insight here is that:

• “The amounts producible from the first half of chemicals”
• “The amounts producible from the second half of chemicals”

can be enumerated separately and then combined at the end.

If the amount produced from the first half is \(s\), then to achieve a total of \(K\), we need the second half to produce \(K-s\).
In other words:

• Enumerate all possible sums from the first half
• Enumerate all possible sums from the second half and store them in a set
• For each \(s\), check whether \(K-s\) exists in the second half’s set

This allows us to determine the answer.

This is a classic form of Meet-in-the-Middle.

Algorithm

1. Split the list of chemicals into the first half left and the second half right (each roughly half in size).
2. For the first half, enumerate all possible total amounts to create sums_left.
   Starting from the initial value [0], for each chemical \((a,b)\):
   • Keep as is (don’t use)
   • +a (normal)
   • +b (heated)

Update accordingly. 3. Similarly, create sums_right for the second half. 4. Convert sums_right to a set for fast lookup. 5. For each s in sums_left, if K - s exists in set_right, output Yes. 6. If nothing is found after checking all values, output No.

Illustrative Example

For example, if the amounts producible from the first half are {0, 2, 5}, the amounts producible from the second half are {0, 3, 7}, and the target is \(K=8\):

• Choosing \(s=5\) from the first half, the required amount from the second half is \(8-5=3\)
• Since \(3\) exists in the second half’s set, it is achievable → Yes

Complexity

• Time complexity: \(O(3^{N/2})\) (more precisely, first half enumeration \(O(3^{n_1})\), second half enumeration \(O(3^{n_2})\), matching \(O(3^{n_1})\))
• Space complexity: \(O(3^{N/2})\)

For \(N \le 26\), \(3^{13}=1,594,323\), which is sufficiently manageable even in Python.

Implementation Notes

• By setting the initial state to sums = [0], the case of “selecting nothing” is naturally included (this also handles \(K=0\)).

• It is important to convert the second half to a set so that in lookups are \(O(1)\) on average.

• Although \(K\) and \(A_i, B_i\) can be large, Python’s integers support arbitrary precision, so there is no need to worry about overflow.

  Source Code

import sys

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

    n1 = N // 2
    n2 = N - n1
    left = AB[:n1]
    right = AB[n1:]

    sums_left = [0]
    for a, b in left:
        new = []
        for s in sums_left:
            new.append(s)        # not used
            new.append(s + a)    # normal mode
            new.append(s + b)    # heated mode
        sums_left = new

    sums_right = [0]
    for a, b in right:
        new = []
        for s in sums_right:
            new.append(s)
            new.append(s + a)
            new.append(s + b)
        sums_right = new

    set_right = set(sums_right)

    for s in sums_left:
        if K - s in set_right:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.