공유 자전거의 마감 배치표

문제

공유 자전거 운영팀의 데이터 담당자는 하루 동안 완료된 이용 기록으로 다음 날의 자전거 재배치 규모를 계산한다. 운영 구역에는 1번부터 M번까지의 대여소가 있다. 모든 이용 기록은 출발 대여소와 도착 대여소를 담은 CSV 행으로 제공된다. 한 행은 자전거 한 대를 빌려 다른 곳 또는 같은 곳에 반납한 이용 한 건이다. 운영팀은 각 대여소의 마감 목표 수량을 그날 영업을 시작할 때의 수량과 같게 정했다. 대여소에서 이용 한 건이 출발하면 그 대여소의 자전거가 한 대 줄고, 이용 한 건이 도착하면 한 대 늘어난다. 출발과 도착이 같은 이용은 해당 대여소의 마감 수량을 바꾸지 않는다. 같은 출발·도착 쌍이 여러 번 나타나면 서로 다른 이용이므로 모두 센다. 기록은 완료된 이용 전체를 담고 있으며, 영업 도중의 자전거 부족 여부는 판단하지 않는다. 각 대여소의 부족량은 출발 횟수에서 도착 횟수를 뺀 값과 0 중 큰 값으로 정의한다. 반대로 도착 횟수가 더 많으면 그 차이만큼 다른 대여소로 보낼 여유가 있다. 운영팀은 여유가 있는 대여소에서 부족한 대여소로 자전거를 직접 옮길 수 있다. 한 대를 출발 대여소에서 목적 대여소까지 옮기는 작업을 이동 한 번으로 세며, 거리와 운반 수단의 적재량은 고려하지 않는다. 외부에서 자전거를 추가하거나 운영 구역 밖으로 내보내지는 않는다. 모든 대여소를 마감 목표 수량으로 되돌리는 데 필요한 최소 이동 횟수를 구한다. 또한 부족량이 가장 큰 대여소와 그 부족량을 구한다. 최대 부족량이 같은 양수인 대여소가 여러 개라면 번호가 가장 작은 대여소를 선택한다. 모든 대여소의 부족량이 0이면 선택할 대여소가 없는 것으로 처리한다.

입력

첫째 줄에 정수 N과 M이 공백으로 주어진다. 1 ≤ N ≤ 40,000, 1 ≤ M ≤ 99이다.
둘째 줄에 CSV 헤더 `from,to`가 주어진다.
이후 N개 줄에 `from,to` 형식의 이용 기록이 주어진다. 두 필드는 모두 1 이상 M 이하의 정수다. 각 필드는 앞에 불필요한 0이 없는 십진수 표기이며, 필드 사이에는 쉼표 하나만 있다. 공백, 따옴표, 빈 필드는 없다. 기록의 행 순서는 결과에 영향을 주지 않는다.

출력

첫째 줄에 모든 대여소를 마감 목표 수량으로 되돌리는 데 필요한 최소 이동 횟수를 출력한다. 둘째 줄에 선택한 대여소 번호와 그 부족량을 공백으로 구분하여 출력한다. 최대 부족량이 같은 양수이면 가장 작은 대여소 번호를 선택한다. 모든 대여소의 부족량이 0이면 둘째 줄에 `0 0`을 출력한다.

6 4
from,to
1,2
1,3
2,3
4,3
4,4
3,2

3
1 2

4 3
from,to
1,2
2,3
3,1
2,2

0
0 0

4 4
from,to
2,4
1,3
2,3
1,4

4
1 2

출처: Devin.KR 자체 제작