사무실

N* 회사의 사무실에는 긴 복도를 따라 여러 개의 방이 있다. 각 방에는 여러 개의 좌석이 있다. N*에는 많은 직원이 있으며, 직원들은 수시로 복도의 한쪽 끝이나 반대쪽 끝으로 심부름을 가야 한다. 생산 측면에서 가장 중요한 장소가 그곳에 있기 때문이다.

어느 시점에 CEO는 배치를 최적화할 때가 되었다고 판단하고 컨설턴트를 고용해 직원들을 좌석에 배치하는 최선의 방법을 알아내게 했다. 먼저 컨설턴트는 복도의 길이를 측정해 $L$임을 확인하고 다음과 같은 기준을 제안했다. 하루 동안 직원들이 복도를 따라 이동하는 총거리가 최소인 배치를 최적으로 본다. 직원이 복도 시작점에서 거리 $p$인 방에서 일한다면, 복도 시작점까지 갔다가 돌아오는 데 거리 $2p$를 이동하고, 복도 끝까지 한 번 갔다가 돌아오는 데는 $2(L-p)$를 이동한다. 추가 분석으로 각 직원이 하루에 복도 시작점과 끝으로 가는 횟수를 알아냈다.

이제 모든 데이터가 준비되었으므로 모든 직원의 최적 배치를 계산해야 한다. 물론 각 방에 배치할 수 있는 직원 수는 그 방의 좌석 수로 제한된다.

첫 줄에 세 정수 $N$, $M$, $L$이 주어진다. $N$은 방의 수 ($1 \le N \le 10^5$), $M$은 직원 수 ($1 \le M \le 10^5$), $L$은 복도의 길이 ($2 \le L \le 10^8$)이다.

다음 $N$개 줄에는 $i$번째 방을 설명하는 두 정수 $P_i$, $C_i$가 주어진다. $P_i$는 복도 시작점에서 $i$번째 방까지의 거리 ($0 < P_i < L$), $C_i$는 $i$번째 방의 좌석 수 ($1 \le C_i \le 10^5$)이다.

다음 $M$개 줄에는 $i$번째 직원을 설명하는 두 정수 $A_i$, $B_i$가 주어진다. 각각 그 직원이 하루에 방에서 복도 시작점으로 가는 횟수와 복도 끝으로 가는 횟수다 ($0 \le A_i, B_i \le 10^5$).

전체 좌석 수는 $10^6$을 넘지 않는다. 모든 직원을 배치할 좌석이 충분함이 보장된다.

첫 줄에 최적 배치에서 직원들이 하루 동안 이동하는 총거리를 정수로 출력한다. 다음 $N$개 줄에는 그런 배치의 정보를 출력한다. $i$번째 줄에는 먼저 $i$번째 방에서 일할 직원 수 $S_i$를 출력하고, 같은 줄에 그 직원들의 번호 $S_i$개를 임의 순서로 출력한다. 가능한 배치가 여러 가지라면 그중 하나를 출력한다. 직원 번호는 입력에 나타난 순서대로 1부터 매긴다.