만국의 노동자여 단결하라! 단, 너무 가까이 말고.

당신은 이름조차 붙일 수 없을 만큼 극비인 프로젝트에 투입된 노동자들을 관리한다. 이들은 그림 1의 왼쪽에 있는 아파트에 각자 따로 거주하며, 매일 아침 같은 시각에 출발해 오른쪽에 있는 작업장 중 하나로 향한다. 집에서 작업장으로 가려면 가운데에 있는 보안 게이트를 지나야 한다. 각 게이트에는 A와 B로 표시된 두 개의 서로 다른 통로가 있다. 그림에서 볼 수 있듯이 각 게이트의 A 통로는 항상 B 통로보다 북쪽에 있다.

그림 1: 아파트, 게이트, 작업장의 배치.

노동자들을 작업장으로 보내는 일은 단순해 보이지만, COVID-$19$가 시작되면서 문제가 생겼다. 첫째, 사회적 거리 두기 때문에 두 노동자가 같은 게이트를 사용할 수 없다. 둘째, 게이트의 배치 때문에 한 노동자가 A 통로를 사용하면 그보다 북쪽 게이트를 사용하는 사람은 B 통로를 사용할 수 없다. 너무 가깝기 때문이다. 노동자가 B 통로를 사용하는 경우에도 비슷한 일이 일어난다. 그보다 남쪽 게이트를 사용하는 노동자는 A 통로를 사용할 수 없다.

당신은 노동자들을 작업장에 배정하는 일을 맡았고, 각 작업장에는 노동자 한 명씩 배정한다. 어느 노동자가 어느 작업장에 배정되는지는 상관없지만, 위에서 설명한 사회적 거리 두기 조건을 지키면서 모든 노동자가 이동하는 총거리를 최소화하려 한다. 게이트 입구와 출구의 특이한 배치 때문에 어떤 게이트에서는 A 통로를 사용할 때와 B 통로를 사용할 때 거리 차이가 크게 날 수 있어서 문제가 복잡해진다. 주어진 모든 상대 거리를 바탕으로, 모든 노동자가 이동하는 총거리를 최소화하는 노동자와 작업장의 배정을 구하라.

입력은 양의 정수 $n \le 50$ 하나가 있는 줄로 시작한다. $n$은 노동자, 게이트, 작업장의 수이며 각각 $1$부터 $n$까지 번호가 붙는다. 이어서 $n$개의 줄이 있고 각 줄에는 $2n$개의 양의 정수가 있다. 이 중 $i$번째 줄은 노동자 $i$에서 $n$개의 게이트 입구까지의 거리를 나타낸다. 처음 두 값은 게이트 $1$의 통로 A와 B까지의 거리이고, 그다음 두 값은 게이트 $2$의 통로 A와 B까지의 거리이며, 이런 식으로 이어진다. 그다음에는 $n$개의 줄이 더 있고 각 줄에는 $2n$개의 양의 정수가 있다. 이 중 $j$번째 줄은 작업장 $j$에서 $n$개의 게이트 출구까지의 거리를 같은 방식으로 나타낸다. 모든 거리는 양수이며 $1\,000$ 이하다.

출력의 첫 줄에는 달성할 수 있는 노동자들의 최소 총 이동 거리를 출력한다. 이어서 각 노동자의 배정을 나타내는 $n$개의 줄을 출력한다. 이 중 $i$번째 줄은 $i$ $g_i$ $w_i$ 형식이며, 노동자 $i$가 게이트 $g_i$를 이용해 작업장 $w_i$로 간다는 뜻이다. 출력 형식은 샘플 출력과 같게 한다. 최적인 배정이 여러 개라면 어느 것이든 허용된다.