Overview

For each chemical, there are \(3\) choices: “don’t use,” “normal mode,” or “heated mode.”
Since a brute-force search of all \(3^N\) combinations is too slow, we split the chemicals into two halves and enumerate each half exhaustively using Meet-in-the-Middle.

Analysis

In this problem, for each chemical there are the following \(3\) choices:

• Don’t use it
• Use it in normal mode (\(A_i\) mL)
• Use it in heated mode (\(B_i\) mL)

Therefore, the total number of combinations is \(3^N\).
However, since \(N \leq 26\),

\[ 3^{26} \approx 2.5 \times 10^{12} \]

which makes it impossible to try all combinations naively.

---

Also, since this is a common type of problem where we need to determine “whether the sum is exactly \(K\),” one might consider DP. However, in this problem,

\[ K \leq 10^{15} \]

which is extremely large, so DP indexed by the sum cannot be used.

---

This is where Meet-in-the-Middle becomes effective.

We split the chemicals into a first half and a second half.
By exhaustively enumerating all “achievable total amounts” for each half, we let:

• \(x\) be an amount achievable by the first half
• \(y\) be an amount achievable by the second half

and check whether there exists a pair such that:

\[ x + y = K \]

---

For example, if we split \(N=26\) into \(13\) and \(13\), the number of combinations for each half is at most:

\[ 3^{13} = 1594323 \]

This is a practical size, so we can enumerate one half and store the results in a set, then enumerate the other half and check whether the complement \(K-y\) exists.

---

Furthermore, in this problem \(A_i, B_i \geq 1\), so if the running total already exceeds \(K\), it can never return to exactly \(K\).
Therefore, during enumeration, we only proceed when:

• \(s + A_i \leq K\)
• \(s + B_i \leq K\)

This eliminates unnecessary searches.

Algorithm

1. Split the chemical list into a first half left and a second half right.
2. For the first half, exhaustively enumerate all \(3\) choices for each chemical:
   • Don’t use it
   • Add \(A_i\)
   • Add \(B_i\)

Store all achievable total amounts in a set called left_sums. 3. Do the same exhaustive enumeration for the second half. 4. When a total amount \(s\) is achievable by the second half, if \(K-s\) is achievable by the first half, then the total is exactly \(K\).
In other words, if

$\( K - s \in \text{left\_sums} \)$

then the answer is Yes. 5. If no such pair is found by the end, the answer is No.

---

In this code, the exhaustive enumeration is done using DFS with a stack rather than recursion.
The state consists of two values:

• Which chemical we have considered up to
• The current total amount

From each state, there are the following 3 transitions:

• Don’t use that chemical
• Use it in normal mode
• Use it in heated mode

---

Illustration

For example, suppose the amounts achievable by the first half are:

\[ \{0, 3, 5, 8\} \]

If during the enumeration of the second half we find that \(s=7\) is achievable, we check whether:

\[ K-s \]

exists in the first half’s set.
If \(K=15\), then \(15-7=8\), so combining \(8\) from the first half and \(7\) from the second half gives us exactly \(15\).

Complexity

• Time complexity: \(O\left(3^{\lfloor N/2 \rfloor} + 3^{\lceil N/2 \rceil}\right)\)
• Space complexity: \(O\left(3^{\lfloor N/2 \rfloor}\right)\)

Since \(N \leq 26\), we only need to perform exhaustive enumeration of roughly \(3^{13}\) twice at most.

Implementation Notes

• Since each chemical has the option of “don’t use,” the initial total of \(0\) is always included.
  This ensures correct handling even when \(K=0\).

• States where the total exceeds \(K\) need not be explored further, since only positive amounts are added from that point on.

• By storing the first half’s total amounts in a set, duplicates are automatically removed.

• This can also be written using recursion, but the code uses a stack for iterative DFS. This avoids concerns about recursion depth.

  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)]

    m = N // 2
    left = AB[:m]
    right = AB[m:]

    left_sums = set()

    stack_i = [0]
    stack_s = [0]
    llen = len(left)

    while stack_i:
        i = stack_i.pop()
        s = stack_s.pop()

        if i == llen:
            left_sums.add(s)
            continue

        a, b = left[i]
        ni = i + 1

        stack_i.append(ni)
        stack_s.append(s)

        x = s + a
        if x <= K:
            stack_i.append(ni)
            stack_s.append(x)

        y = s + b
        if y <= K:
            stack_i.append(ni)
            stack_s.append(y)

    stack_i = [0]
    stack_s = [0]
    rlen = len(right)

    while stack_i:
        i = stack_i.pop()
        s = stack_s.pop()

        if i == rlen:
            if K - s in left_sums:
                print("Yes")
                return
            continue

        a, b = right[i]
        ni = i + 1

        stack_i.append(ni)
        stack_s.append(s)

        x = s + a
        if x <= K:
            stack_i.append(ni)
            stack_s.append(x)

        y = s + b
        if y <= K:
            stack_i.append(ni)
            stack_s.append(y)

    print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.