영 타블로가 싫은 재우

2023년이 되고, 전년도의 활동을 통해 MatKor는 학부동아리로 승격되었다. 특히 <제2회 MatKor Cup:2023 Winter>가 끝나고 대회 검수자였던 종우, 대회에서 뛰어난 성적으로 입상한 세준이, 대회가 끝난 후 한 문제를 빼고 모두 업솔빙한 하늘이가 MatKor에 합류했다. 인원이 많아진 MatKor는 이때부터 세미나 분반을 실력별로 초, 중, 고급으로 나누어 세미나를 진행하게 되었다.

MatKor에서는 동아리가 설립된 2022년부터 지금까지 한 번도 빠짐없이 세미나 주제 중에 영 타블로가 있다. 매년 동우의 영 타블로 수업을 듣던 재우는 화가 나 이제 영 타블로를 없애버리고자 한다.

영 타블로는 정수로 이루어진 $\lambda =\left( \lambda\_1,\lambda\_2,\cdots ,\lambda\_H \right)$로 나타낼 수 있다. 이는 높이가 $H$이고, $1$행 부터 순서대로 $H$행까지 각 행의 길이가 $\lambda\_i$인 모양을 의미하는데, $\lambda\_1\ge\lambda\_2\ge\cdots\ge\lambda\_H\ge 1$을 만족해야 한다. 예를 들어 영 타블로 $\lambda =\left( 5,4,1 \right)$은 다음을 의미한다.

동우는 재우에게 처음에 높이가 $H$로 동일한 영 타블로 $N$개를 주었다. 또한, $N$개의 영 타블로 중 합칠 수 있는 $M$개의 쌍을 주었다. 이제 재우는 아래 행동을 반복하여 모든 영 타블로를 직사각형으로 만들고자 한다. 재우는 한 번 행동할 때, 아래 중 하나를 할 수 있다. 편의상 존재하지 않는 행인 $H+1$ 이상의 $i$에 대해 $\lambda\_i=0$이라 하자.

• 행동 1

  • 영 타블로 하나와 해당 영 타블로의 행 하나를 고른다.
  • 이때, 고른 행을 $r$행 이라 하면, $\lambda\_r\gt\lambda\_{r+1}$과 $\lambda\_r\ge 2$를 만족해야 한다.
  • $c$의 비용을 들여 해당 행의 마지막 열의 칸을 지운다.

• 행동 2

  • 영 타블로 하나와 해당 영 타블로의 행 하나를 고른다.
  • 이때, 고른 행을 $r$행 이라 하면, $r=1$ 혹은 $\lambda\_r\lt\lambda\_{r-1}$을 만족해야 한다.
  • $d$의 비용을 들여 해당 행의 마지막 열 뒤에 칸을 하나 추가한다.

• 행동 3

  • 합칠 수 있는 영 타블로 쌍인 $i$, $j(i\ne j)$번 영 타블로를 골라 둘 중 하나를 $180^{\circ}$ 돌려서 다른 하나와 맞춘다.

  • 이때, 칸이 남거나 겹치면 안 되며, 비용은 발생하지 않는다.

    • 구체적으로, 두 영 타블로의 높이는 동일해야 하며, 이 높이를 $h$라고 할 때 다음을 만족해야 한다.
    • $a$번 영타블로가 $\left( \lambda\_{1}^a,\lambda\_2^a,\cdots ,\lambda\_h^a \right)$, $b$번 영타블로가 $\left( \lambda\_{1}^b,\lambda\_2^b,\cdots ,\lambda\_h^b \right)$라고 하면, $1\le k\le h$인 모든 정수 $k$에 대해 $\lambda\_k^a+\lambda\_{h-k+1}^b$가 동일하다.

  • 이 행동 이후 두 영 타블로는 하나의 직사각형이 되며, 두 영 타블로는 더 이상 행동에서 선택될 수 없다.

재우는 위의 행동을 원하는 만큼 반복하여 모든 영 타블로를 직사각형으로 만들고 싶다. 이를 위해 필요한 최소 비용과 그 과정을 구해보자. 최종적인 비용은 모든 행동에서 소모된 비용의 합이며, 행동 3을 통해 두 영 타블로를 합치지 않더라도 행동 1이나 행동 2만 사용하여 영 타블로 하나를 하나의 직사각형으로 만들 수 있다는 점에 유의하자.

첫 번째 줄에 영 타블로의 개수 $N(1\le N\le 5\\, 000)$, 합칠 수 있는 영 타블로의 쌍의 개수 $M(0\le M\le\min\left( 10^4,\frac{n(n-1)}{2} \right))$, 영 타블로의 높이 $H(1\le H\le 500)$가 공백으로 구분되어 주어진다.

두 번째 줄에 비용을 의미하는 정수 $c$, $d(1\le c,d\le 3\\, 000)$가 공백으로 구분되어 주어진다.

세 번째 줄부터 $N$개의 줄에 걸쳐 $1$번 부터 $N$번 영 타블로의 초기 상태를 의미하는 $H$개의 정수 $\lambda\_{1}^i,\lambda\_2^i,\cdots ,\lambda\_H^i(10^6\ge\lambda\_1^i\ge\lambda\_2^i\ge\cdots\ge\lambda\_H^i\ge 1)$가 공백으로 구분되어 한 줄에 영 타블로가 한 개씩 주어진다.

$N+3$ 번째 줄부터 $M$개의 줄에 걸쳐 합칠 수 있는 영 타블로 쌍 $a\_i,b\_i(1\le a\_i, b\_i\le N$; $a\_i \ne b\_i)$가 한 줄에 하나씩 공백으로 구분되어 주어진다. 같은 쌍은 여러 번 주어지지 않는다.

첫 번째 줄에 재우가 모든 영 타블로를 없애거나 남아있는 모든 영 타블로를 직사각형으로 만들기 위해 필요한 최소 비용을 출력한다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $1$번부터 $N$번 영 타블로에 대해 $i$번 영 타블로의 최종 상태를 의미하는 두 개의 정수 $c\_i,m\_i$를 공백으로 구분하여 출력한다. 이는 다음과 같다.

• 만약 해당 영 타블로가 행동 3에 영향을 받지 않고, 자기 자신이 직사각형이 되었다면, 가로를 $c\_i$로 하고, $m\_i=i$으로 한다.
• 만약 해당 영 타블로가 행동 3으로 합쳐졌다면, 최종 상태에서 합쳐진 직사각형의 가로를 $c\_i$로 하고, $m\_i$는 행동 3에서 합쳐진 다른 영 타블로의 번호로 한다.