트리 변환 최소 비용

두 개의 가중치가 있는 뿌리 있는 트리가 주어진다. 각 정점의 자식은 순서가 정해져 있으며 왼쪽에서 오른쪽으로 배열된다. 기본 연산은 네 가지다.

1. 성장: 정점 $x$의 자식 리스트가 $y_1, \ldots, y_m$일 때, 새 정점 $z$를 추가하고 $x$와 $z$를 잇는 간선을 만든다. 그다음 $z$를 자식 리스트의 $k$번째 위치에 넣어 리스트가 $y_1, \ldots, y_{k-1}, z, y_k, \ldots, y_m$이 되게 한다. 비용은 새 간선 $(x, z)$의 가중치에 $c_1$을 곱한 값이다.

2. 확장: 정점 $x$의 자식 리스트가 $y_1, \ldots, y_m$일 때, 구간 $[l, r]$ ($1 \le l \le r \le m$)을 고른다. 새 정점 $z$를 $y_l, \ldots, y_r$의 부모로 추가하고 $x$와 $z$를 잇는다. $x$의 자식 리스트는 $y_1, \ldots, y_{l-1}, z, y_{r+1}, \ldots, y_m$이 되고, $z$의 자식 리스트는 $y_l, \ldots, y_r$이 된다. 간선 $(z, y_i)$의 가중치는 원래 트리의 $(x, y_i)$와 같다. 비용은 새 간선 $(x, z)$의 가중치에 $c_1$을 곱한 값이다.

3. 축약: 정점 $x$의 자식 $y_k$를 하나 고른다. $y_k$의 자식 리스트가 $z_1, \ldots, z_p$일 때 간선 $(x, y_k)$를 축약한다. $y_k$는 제거되고, $x$의 자식 리스트는 $y_1, \ldots, y_{k-1}, z_1, \ldots, z_p, y_{k+1}, \ldots, y_m$이 된다. 간선 $(x, z_i)$의 가중치는 $(y_k, z_i)$의 가중치와 같다. 비용은 원래 트리에서 간선 $(x, y_k)$의 가중치에 $c_2$를 곱한 값이다.

4. 가중치 변경: 정점 $x$와 그 자식 $y$에 대해 간선 $(x, y)$의 가중치를 $w_1$에서 $w_2$로 바꾼다. 비용은 $c_3 \cdot |w_1 - w_2|$다.

성장이나 확장으로 추가된 간선 $(x, z)$는 가중치를 바꿀 수 없다. 가중치를 바꾼 간선은 축약할 수 없다.

첫 번째 트리를 두 번째 트리로 바꾸는 최소 비용을 구한다. 뿌리와 자식 순서를 보존하는 정점 간 전단사 대응이 있고, 대응하는 간선의 가중치가 모두 같으면 두 트리는 같은 트리로 본다.

첫 줄에 세 정수 $c_1$, $c_2$, $c_3$ ($1 \le c_1, c_2, c_3 \le 10^6$)이 주어진다. 이어서 두 트리가 주어진다. 각 트리마다 첫 줄에 정점 수 $n$이 있고, 다음 $n$개의 줄에는 자식 수 $k$와 $2k$개의 정수 $c_1, w_1, \ldots, c_k, w_k$ ($0 \le c_i \le 10^6$)가 차례로 적혀 있다. 이는 자식 리스트와 자식으로 향하는 간선의 가중치다.

첫 번째 트리의 정점 수는 50 이하이고, 두 번째 트리의 정점 수는 2000 이하다.

답을 출력한다.