택배 상자 짝 맞추기

문제

한 물류센터에 택배 물품이 N개 쌓여 있다. 물품에는 B가지 취급 속성(냉동, 액체, 파손 주의 등)이 있으며, i번째 물품이 가진 속성은 B비트 정수 a_i로 주어진다. a_i의 j번째 비트(0번째부터 B-1번째까지)가 1이면 그 물품은 j번 속성을 가진다. 같은 속성을 가진 두 물품을 한 상자에 함께 담으면 서로 취급 방법이 충돌하므로, 한 상자에 담을 수 있는 두 물품은 공통으로 가진 속성이 하나도 없어야 한다. 즉 a_i AND a_j = 0 이어야 한다. 속성이 하나도 없는 물품(a_i = 0)은 다른 어떤 물품과도 함께 담을 수 있다. 물품 i를 운송하는 데 드는 운임은 w_i이다. 센터는 서로 다른 두 물품을 골라 한 상자에 담아 보내려 하며, 이때 상자의 운임은 두 물품의 운임의 합이다. 담을 수 있는 쌍 중 운임의 합이 가장 큰 값을 구하는 프로그램을 작성한다. 같은 물품을 두 번 고를 수는 없지만, 속성과 운임이 같은 서로 다른 물품은 따로 센다. 조건을 만족하는 쌍이 하나도 없으면 -1을 출력한다.

입력

첫 줄에 물품 수 N과 속성 수 B가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000, 1 ≤ B ≤ 14) 다음 N개의 줄에 각각 정수 a_i와 w_i가 공백으로 구분되어 주어진다. (0 ≤ a_i < 2^B, 1 ≤ w_i ≤ 1,000,000,000)

출력

가능한 쌍의 운임 합의 최댓값을 한 줄에 출력한다. 가능한 쌍이 없으면 -1을 출력한다.

4 3
5 10
2 7
6 20
1 4

24

2 2
0 3
0 9

12

2 2
3 5
3 6

-1

출처: Devin.KR 자체 제작