Cho một dãy gồm \(N\) số nguyên không âm \(a_1, a_2, \dots, a_N\). Bạn cần phân chia dãy số này thành đúng \(K\) đoạn con liên tiếp, không rỗng.

Mỗi đoạn con \(a[l..r]\) có chi phí nén là giá trị XOR tích lũy của tất cả các phần tử trong đoạn: \(\text{cost}(l, r) = a_l \oplus a_{l+1} \oplus \dots \oplus a_r\)

Tổng chi phí của cách chia là tổng chi phí của cả \(K\) đoạn con. Hãy tìm cách phân chia sao cho tổng chi phí là nhỏ nhất.

Định dạng đầu vào

• Dòng thứ nhất chứa hai số nguyên \(N\) và K (\(1 \le K \le 200, K \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i < 2^{30}\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Ví dụ

Input:

5 2
1 2 3 4 5

Output:

1

Giải thích: Chia thành 2 đoạn: \([1, 2, 3]\) và \([4, 5]\).

• Chi phí đoạn 1: \(1 \oplus 2 \oplus 3 = 0\).
• Chi phí đoạn 2: \(4 \oplus 5 = 1\).
• Tổng chi phí: \(0 + 1 = 1\).

Ràng buộc & Subtasks