부가 서비스를 채우는 항공권

문제

여행사 직원 하은이는 한 고객의 여행에 쓸 항공권을 고르려 한다. 고객이 반드시 받아야 하는 부가 서비스는 K종류이며 0번부터 K-1번까지 번호가 붙어 있다. 판매 중인 항공권은 N장이고, i번째 항공권은 가격 p_i원에 일부 부가 서비스를 묶어서 제공한다. 제공하는 서비스는 정수 m_i로 나타낸다. m_i를 이진수로 썼을 때 2^j 자리가 1이면 그 항공권이 j번 서비스를 제공한다는 뜻이다. 고객은 항공권을 한 장 또는 두 장 산다. 두 장을 산다면 서로 다른 두 장이어야 하며, 두 장이 같은 서비스를 중복해서 제공해도 상관없다. 구매한 항공권이 제공하는 서비스를 모두 합쳤을 때 K종류가 전부 포함되어야 한다. 이 조건을 만족하는 구매 중 가격의 합이 최소인 값을 구하는 프로그램을 작성하라. 조건을 만족하는 구매가 없으면 -1을 출력한다. 서비스를 하나도 제공하지 않는 항공권(m_i=0)도 있을 수 있고, 같은 가격이나 같은 m_i를 가진 항공권이 여러 장 있을 수도 있다. N이 크므로 모든 쌍을 직접 확인하는 방법은 시간 안에 끝나지 않는다. 가격은 모두 양의 정수이고 답도 정수이다.

입력

첫 줄에 항공권 수 N과 서비스 종류 수 K가 공백으로 구분되어 주어진다. 이어지는 N개의 줄에 i번째 항공권의 가격 p_i와 서비스 정수 m_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ 16, 1 ≤ p_i ≤ 10^9, 0 ≤ m_i < 2^K 이다.

출력

조건을 만족하는 구매의 최소 가격 합을 한 줄에 출력한다. 조건을 만족하는 구매가 없으면 -1을 출력한다.

4 3
50 3
40 4
70 7
30 5

70

2 2
10 1
20 1

-1

3 2
5 1
6 2
100 3

11

출처: Devin.KR 자체 제작