Consider solving the problem without explicitly maintaining a Trie.

For an integer \(k\), an integer \(M\) not greater than \(2^k\), and a set \(A\) of integers whose elements are all less than \(2^k\), define \(\displaystyle f(A,M,k)=\sum_{x =0}^{M-1} \min_i (x \oplus A_i)\). What we want is \(f(A,M,30)\).

We will compute this value \( f(A,M,k)\) recursively.

First, if \(k=0\) or \(M=0\), then \(f(A,M,k)=0\). From now on, we consider other cases.

Define sets \(B_0\) and \(B_1\) as \(B_0=\lbrace 0\le x < 2^{k-1}| x \in A\rbrace\) and \(B_1=\lbrace 0\le (x - 2^{k-1}) < 2^{k-1}| x \in A\rbrace\), respectively. (Intuitively, \(B_0\) is the set of elements in \(A\) less than \(2^{k-1}\), and \(B_1\) is those not less than \(2^{k-1}\), subtracted by \(2^{k-1}\).)

1. If \(M=2^k\)

If \(B_0\) and \(B_1\) are both non-empty, the answer is \(\displaystyle f(B_0,2^{k-1},k-1)+f(B_1,2^{k-1},k-1)\).

If \(B_0\) is only empty, the answer is \(\displaystyle 2f(B_1,2^{k-1},k-1)+2^{2k-2}\). If \(B_1\) is only nonempty, then it is similarly \(\displaystyle 2f(B_0,2^{k-1},k-1)+2^{2k-2}\).

2. If \(M \le 2^{k-1}\)

If \(B_0\) is empty, the answer is \(f(B_1,M,k-1) + M2^{k-1}\).

If it is empty, then any element from \(B_1\) is not eligible for the minimum value. Thus, the answer is \(\displaystyle f(B_0,M,k-1)\).

3. If \( 2^{k-1} < M < 2^k\)

The contribution of the elements with \(0\le x < 2^{k-1}\) is \(f(B_1,2^{k-1},k-1) + 2^{2k-2}\) if \(B_0\) is empty, and \(f(B_0,2^{k-1},k-1)\) otherwise.

The contribution of the elements with \(2^{k-1}\le x < M\) is \(f(B_0,M-2^{k-1},k-1) + 2^{k-1}(M-2^{k-1})\) if \(B_1\) is empty, and \(f(B_1,M-2^{k-1},k-1)\) otherwise.

The sought value is the sum of these two values.

The problem can be solved by implementing the relations above appropriately. The complexity is \(O(N\log \max A)\).

Sample code (Python 3)

def f(A, M, k):
    if k == 0:
        return 0
    B = [[], []]
    for i in A:
        B[(i >> (k - 1)) & 1].append(i & ~(1 << (k - 1)))
    mid = 1 << (k - 1)
    if M == 1 << k:
        if B[0] and B[1]:
            return f(B[0], mid, k - 1) + f(B[1], mid, k - 1)
        return 2 * f(A, mid, k - 1) + mid * mid
    ans = f(B[0], min(M, mid), k - 1) if B[0] else f(A, min(M, mid), k - 1) + mid * min(M, mid)
    if M > mid:
        ans += f(B[1], M - mid, k - 1) if B[1] else f(A, M - mid, k - 1) + mid * (M - mid)
    return ans

N, M = map(int,input().split())
A = list(map(int,input().split()))
print(f(A, M, 30))