25322번 - 편지 배달 스페셜 저지

UCPC 중학교에서는 다른 반에 있는 친구에게 편지를 보내는 것이 유행이다. UCPC 중학교에는 $1$반부터 $N$반까지 총 $N$개의 반이 있고, 각 반의 교실은 반 번호 순서대로 긴 복도를 따라 나열되어 있다. $i$반 교실의 위치는 복도의 시작점으로부터의 거리를 나타내는 정수 $x_i$로 표현된다.

동규는 편지 유행이 좋은 사업 기회라고 생각해서 편지 배달 서비스를 기획했다. 학생들이 앱을 통해 편지 배송 요청을 접수하면, 쉬는 시간에 일괄적으로 편지를 배달해 주는 서비스이다. 각 편지 배송 요청에는 $1$번부터 $M$번까지 번호가 붙어 있으며, 출발지와 목적지의 반 번호 쌍 $(s_i,e_i)$가 적혀 있다.

동규는 원활한 배달을 위해 각 반에서 한 명씩을 뽑아 배달원으로 고용했다. 동규가 배달원들에게 편지 배송 요청을 적절히 배분해 주면, 각 배달원은 그에 따라 편지를 배달하고 동규에게 수당을 받는다. 자세한 규칙은 다음과 같다.

• 각 배달원은 동규가 정해준 순서대로 편지를 배달해야 한다.
• 배달원이 둘 이상의 편지를 지니면 편지가 섞일 수 있으므로 한 번에 하나의 편지만 배달할 수 있다.
• 배달원이 배달을 모두 마치고 나면 수업을 들어야 하기 때문에 다시 자기 반 교실로 돌아와야 한다.
• 각 배달원은 자기 반 교실에서 출발해서 편지를 모두 배달하고 자기 반 교실로 돌아오는 데 필요한 최소 이동 거리만큼 동규에게 수당을 받는다.
• 편지 배송 요청을 배분받지 않은 배달원들은 수당을 받지 않는다.

예를 들어, $4$개의 반 교실이 $1$의 간격을 두고 나란히 있고, 배달해야 하는 편지의 출발지와 목적지 쌍이 순서대로 $(4,2)$, $(1,3)$이라고 하자.

만약 1반의 배달원에게 2번 편지를 배분하고 3반의 배달원에게 1번 편지를 배분한다면, 1반의 배달원이 이동해야 하는 거리는 $2+2=4$이고 3반의 배달원이 이동해야 하는 거리는 $1+2+1=4$이다. 따라서 동규는 두 배달원에게 총 $4+4=8$의 수당을 지급해야 한다. (그림 I.1)

한편, 2, 3, 4반의 배달원들에게는 편지를 배분하지 않고 1반의 배달원에게 2, 1번 편지를 순서대로 배분한다면, 1반의 배달원이 이동해야 하는 거리는 $2+1+2+1=6$이 된다. 따라서 동규는 1반의 배달원에게만 $6$의 수당을 지급하면 된다. (그림 I.2)

그림 I.1: 동규가 $8$의 수당을 지급해야 하는 배분 방식	그림 I.2: 동규가 $6$의 수당을 지급해야 하는 배분 방식

동규는 배달원들에게 지급할 총 수당을 최소화하고 싶다. 위 예시의 경우, 1반의 배달원에게만 2, 1번 편지를 순서대로 배분했을 때 동규가 지급할 총 수당이 최소가 된다. 배달원들에게 편지 배송 요청을 어떻게 배분해야 하는지 구하시오.

첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(2\leq N\leq 300\, 000$; $1\leq M\leq 300\, 000)$

두 번째 줄에 $N$개의 서로 다른 정수 $x_i$가 공백으로 구분되어 오름차순으로 주어진다. $i$번째 정수는 $i$반의 교실 위치를 나타낸다. $(0\leq x_i\leq 10^9)$

세 번째 줄부터 다음 $M$개의 각 줄에 정수 $s_i$, $e_i$가 공백으로 구분되어 주어진다. $(1\le s_i,e_i\le N;$ $s_i\neq e_i)$ 이 중 $i$번째 줄은 $i$번 편지 배송 요청을 나타내며, $s_i$는 출발지 교실의 반 번호, $e_i$는 목적지 교실의 반 번호이다.

첫 번째 줄에 동규가 지급해야 하는 총 수당의 최솟값을 출력한다.

그 다음 $N$개의 줄을 출력한다. 이 중 $i$번째 줄에는 $i$반 배달원이 동규에게 받을 편지 배송 요청의 개수를 출력한 뒤, 동규에게 받을 편지 배송 요청의 번호를 순서대로 출력한다.

가능한 배분 방법이 여러 가지라면 하나만 출력한다.