관측 기록의 한 자리 보정

문제

천문대의 관측 장치는 별빛의 세기를 0부터 9까지의 정수 한 자리로 저장한다. 장치를 점검하던 연구원은 어느 날의 기록 전체에 같은 보정값을 적용해야 한다는 사실을 알아냈다. 보정값 d는 0 이상 9 이하의 정수이며, 원래 기록 a에 보정값을 적용한 결과는 a+d를 10으로 나눈 나머지다. 예를 들어 원래 기록이 8이고 보정값이 4이면 보정한 기록은 2가 된다. 보정값은 관측마다 따로 고르는 것이 아니라 모든 기록에 하나만 공통으로 적용한다. 연구원에게는 N개의 점검 기록이 있다. 각 점검 기록에는 장치가 저장한 값 a와 같은 순간에 기준 장치가 측정한 값 b가 들어 있다. 어떤 보정값을 적용한 결과가 b와 정확히 같으면 그 점검 기록이 일치한다고 한다. 값의 차이가 작더라도 서로 다르면 일치하지 않는다. 같은 두 값으로 이루어진 점검 기록이 여러 번 등장할 수 있으며, 이들은 각각 별개의 기록으로 센다. 기록이 입력된 순서는 일치 개수에 영향을 주지 않는다. 천문대는 일치하는 기록이 적어도 T개인 보정값만 사용할 수 있다. 사용할 수 있는 보정값 중에서 일치하는 기록의 개수가 가장 많은 값을 선택한다. 가장 많은 일치 개수를 만드는 보정값이 여러 개이면 그중 숫자가 가장 작은 값을 선택한다. T가 0이면 모든 보정값이 사용 조건을 만족하지만, 이때도 일치 개수와 숫자에 관한 선택 규칙을 그대로 적용한다. 사용할 수 있는 보정값이 하나도 없다면 보정에 실패한 것으로 처리한다. 주어진 점검 기록을 이용하여 선택할 보정값과 그 보정값으로 일치하는 기록의 개수를 구한다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 1 ≤ N ≤ 10,000, 0 ≤ T ≤ N이다.
다음 N개의 줄에 정수 a와 b가 공백으로 주어진다. 0 ≤ a, b ≤ 9이다.

출력

사용할 수 있는 보정값이 있으면 선택한 보정값과 일치하는 기록의 개수를 공백으로 구분하여 한 줄에 출력한다. 사용할 수 있는 보정값이 없으면 -1만 출력한다.

5 2
8 1
0 3
5 8
9 0
4 5

3 3

4 2
0 2
8 0
1 6
4 9

2 2

3 2
0 0
0 1
0 2

-1

출처: Devin.KR 자체 제작