30522번 - OR & XOR (Small)

문제

Small 버전에서는 $A_i,ドル $B_j$의 상한이 2ドル^{10}$으로 주어진다.

길이가 $N$인 수열 $A_1, A_2, \cdots, A_N,ドル 수열 $B_1, B_2, \cdots, B_N$ 과 정수 $p$가 주어진다.

$$\sum_{i=1}^N,円 \sum_{j=1}^N,円 (A_i \oplus B_j)$$

$\oplus$는 Bitwise XOR 연산을 의미한다.

위의 수식을 전개했을 때 나타나는 $N^{2}$개의 Bitwise XOR 연산 중 $p$개를 Bitwise OR 연산으로 변경할 때, 가능한 수식의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $N$과 정수 $p$가 공백으로 구분되어 주어진다.

둘째 줄에 수열 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

셋째 줄에 수열 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

출력

문제에서 요구하는 값을 출력한다.

제한

• 1ドル \le N \le 200\ 000$
• 0ドル \le p \le N^2$
• 0ドル \le A_i, B_j < 2^{10}$
• $A_i, B_j$는 정수

힌트