자전거 회수 거점

문제

공유 자전거 운영팀은 하루 동안 사용된 자전거를 점검하기 위해 임시 회수 거점 하나를 정하려고 한다. 운영 구역의 길은 곧은 선으로 나타낼 수 있고, 길 위의 위치는 기준점에서부터의 거리를 나타내는 정수 좌표로 표시한다. 운영팀은 미리 정해 놓은 후보 장소 중 정확히 한 곳을 회수 거점으로 선택해야 한다. 현재 회수할 자전거는 N대이고, 거점 후보는 M곳이다. 후보에는 입력에 주어진 순서대로 1번부터 M번까지 번호가 붙어 있다. 후보의 좌표가 작은 순서대로 번호가 붙는 것은 아니다. 서로 다른 후보가 같은 좌표에 있을 수도 있으며, 이 경우에도 번호가 다른 별개의 후보로 취급한다. 좌표 x에 있는 자전거 한 대를 좌표 p의 거점으로 옮기는 데 드는 이동량은 |x-p|이다. 전체 이동량은 모든 자전거에 대해 이 값을 계산하여 더한 수이다. 운영팀은 각 자전거를 현재 위치에서 선택한 거점까지 따로 옮긴다고 가정한다. 여러 자전거를 한꺼번에 운반하거나, 한 자전거를 옮긴 뒤 다른 자전거 위치로 이동하는 비용은 고려하지 않는다. 같은 좌표에 자전거가 여러 대 있다면 각 자전거의 이동량을 각각 더한다. 거점과 같은 좌표에 있는 자전거의 이동량은 0이다. 후보 장소에 원래 자전거가 있는지와 관계없이 그 후보를 선택할 수 있고, 한 거점이 받아들일 수 있는 자전거 수에는 제한이 없다. 운영팀의 목표는 전체 이동량이 가장 작은 후보를 선택하는 것이다. 전체 이동량이 같은 후보가 여러 곳이면 후보 번호가 가장 작은 곳을 선택한다. 후보가 적어도 한 곳 주어지므로 선택할 후보가 없는 경우는 발생하지 않는다. 주어진 모든 후보에 대해 자전거를 모았을 때의 전체 이동량을 비교하고, 선택한 후보 번호와 그때의 전체 이동량을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 30000, 1 ≤ M ≤ 8이다.
둘째 줄에 후보 좌표 P_1, P_2, ..., P_M이 후보 번호 순서대로 주어진다.
셋째 줄에 자전거 좌표 X_1, X_2, ..., X_N이 주어진다.
모든 좌표는 0 이상 9999 이하의 정수이다. 후보 좌표와 자전거 좌표에는 각각 같은 값이 여러 번 나타날 수 있다.

출력

선택한 후보 번호와 그 후보의 전체 이동량을 공백으로 구분하여 한 줄에 출력한다. 전체 이동량이 같으면 번호가 가장 작은 후보를 선택한다.

4 3
0 5 10
1 4 8 9

2 12

2 2
3 7
5 5

1 4

3 1
6
6 6 6

1 0

출처: Devin.KR 자체 제작