Suppose we want to make lowest bits \(0, \ldots, k\) of \(X\) equal to those of \(T\).

• If throughout the process no increment results in a carry from bit \(k - 1\) to bit \(k\), then bit \(k\) is only affected by XORs, so we want to match bits \(0, \ldots, k - 1\), and ensure that XORs we make also set bit \(k\).
• If there is a carry from bit \(k -1\) to bit \(k\), then, after the carry, bits \(0, \ldots, k - 1\) are set to \(0\). After this, we can consider going from \(0\) to \(T\).

We can see that the bigger problem boils down to smaller ones with different starts and targets, and we want to keep track of how XORs affect higher bits. To avoid keeping track of large carries, we will limit the scope of a subproblem to a single carry beyond the current bit number.

Formally, we define a subproblem \((k, s, f, M)\) as follows:

• \(k\) is the number of lowest bits we want to match.
• \(s\) defines the initial value of \(X\) in the subproblem.
  • if \(s = 0\), then initially \(X = S\).
  • if \(s = 1\), then initially \(X = 0\).
• \(f\) defines the target value of \(X\), as well as carry constraints.
  • If \(f = 0\), then the target is \(T\), and we do not allow any carry between bits \(k - 1 \to k\).
  • If \(f = 1\), then the target is \(0\), and we require the only carry \(k - 1 \to k\) to happen on the last operation (which thus has to be an increment).
• \(M\) is a bitmask of size \(n\). If \(M_i = 0\) (resp. \(1\)), then we require to apply the operation \(X \to X \oplus Y_i\) an even (resp. odd) number of times.

Define \(cost(k, s, f, M)\) as the smallest cost to solve the subprolem described above. The answer is \(\min_M cost(B, 0, 0, M)\), where \(B = 40\) is the number of bits.

We compute all \(cost(k, \ldots)\) by increasing of \(k\). When \(k = 0\), we don’t have to match anything. Still, \(cost(0, s, 0, M) = \sum_{i \in M} C_i\), \(cost(0, s, 1, M) = A + \sum_{i \in M} C_i\) (adding \(1\) can be treated as a carry between bits \(-1 \to 0\)).

We subdivide solutions to \((k + 1, s, f, M)\) based on carries \(k - 1 \to k\). Then, possible solutions can look as follows:

• For any \(s, M\), if applying XORs in \(M\) correctly sets bit \(k\) in \(X\), then \((k, s, 0, M)\) solves \((k + 1, s, 0, M)\).
• In all other cases at least one carry \(k - 1 \to k\) has to happen. Thus, a solution is given by a sequence \((k, s, 1, M_0)\), \((k, 1, 1, M_1)\), \(\ldots\), \((k, 1, f, M_t)\). Note that, knowing \(M_i\), we can keep track of bit \(k\) of \(X\) between the subproblems, and make sure that carries \(k \to k + 1\) happen only when they should.

Thus, finding \(cost(k, s, f, M)\) boils down to constructing an optimal sequence of subproblems. This is a shortest path problem, in a graph where edges are subproblems \((k - 1, s, f, M)\) as described above, and vertices \((x, M)\) describe intermediate states:

• \(x\) is bit \(k\) of \(X\) before the next subproblem,
• \(M\) is the currently accumulated bitmask.

Shortest paths can be found e.g. with Dijkstra. In fact, one can prove that at most one transition of the type \((k, 1, 1, M_i)\) is always enough, but this is not necessary to solve the problem, nor is it helpful to speed up the solution.

Complexity of this solution is \(O(B 2^{2N})\).

Note that if a solution exists, then the answer does not exceed \(2 \cdot 10^{17}\), since there is always a solution involving at most \(2^{40}\) increments and two XORs.