시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 42 19 11 47.826%

문제

차영훈은 스티커 수집가이다. 그는 스티커를 박스에 보관한다. 물론 김지민처럼 아무렇게나 보관하는 것은 아니고, 순서를 정해서 정리한다.

어느날 차영훈의 동생 임문빈이 그의 스티커를 가지고 놀았다. 스티커를 모두 가지고 논 후에 임문빈은 박스에 아무렇게나 넣어버렸다. 따라서 어떤 박스에는 다른 색의 스티커가 같이 있을 수도 있다.

차영훈은 다음과 같은 조건을 만족하게 스터키를 다시 정리하려고 한다.

1. 많아야 한 박스는 조커 박스이다. 이 박스에는 다른 색의 스티커를 보관할 수 있다.

2. 조커 박스를 제외한 모든 박스는 비어있거나, 같은 색의 스티커만을 보관해야 한다.

3. 같은 색을 가진 모든 스티커 (조커 박스에 들어있는 스티커는 제외)는 모두 같은 박스에 있어야 한다.

현재 박스에 어떤 색의 스티커가 몇 개 들어있는 지가 주어질 때, 몇 번 움직여야 위의 조건을 만족하게 스티커를 정리하는지 구하는 프로그램을 자성하시오.

움직임이란 한 박스에서 몇 개의 스티커 (모두 같은 색일 필요는 없다)를 뺀 후에 다른 박스에 모두 넣는 것을 말한다.

입력

첫째 줄에 박스의 개수 N과 스티커 색의 개수 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 색을 가진 스티커가 각 박스에 몇 개 들어있는지 주어진다. 이 값은 9보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 정답을 출력한다. 만약 불가능하면 -1을 출력한다.

예제 입력

3 2
1 1
1 1
1 0

예제 출력

1

힌트

출처