등껍질의 계절

아주 오래 산 거북이의 등껍질에는 빗물이 흐르는 통로가 새겨져 있다. 통로들은 $1$번 정점을 루트로 하는 순서가 있는 루트 트리를 이룬다. 물방울은 루트에서 출발하여 통로를 따라 내려가고, 어떤 리프에 도착하면 그 리프가 물방울을 받는다.

각 내부 정점 $v$에는 자식 통로 중 하나를 가리키는 회전판이 있다. $v$의 자식이 입력에서 주어진 순서대로

라 하자. 물방울 하나가 $v$에 도착하면 다음 일이 순서대로 일어난다.

• 물방울은 회전판이 현재 가리키는 자식 통로를 따라 내려간다.
• 회전판은 다음 자식 통로를 가리키도록 한 칸 회전한다. $c_{v,d_v}$ 다음 통로는 $c_{v,1}$이다.

물방울은 하나씩 떨어진다. 하나의 물방울이 리프에 도착한 뒤에 다음 물방울이 루트에서 출발한다.

거북이가 사는 동안 비는 총 $S$번의 계절에 걸쳐 내린다. $t$번째 계절에는 정확히 $X_t$개의 물방울이 루트에 차례대로 떨어진다. 한 계절이 끝나도 어떤 회전판도 초기화되지 않으며, 모든 회전판의 상태는 다음 계절까지 그대로 유지된다.

첫 번째 계절이 시작되기 전에, 각 내부 정점의 회전판이 처음 가리킬 자식 통로를 서로 독립적으로 자유롭게 정할 수 있다. 첫 번째 물방울이 떨어진 뒤에는 회전판을 직접 조작할 수 없다.

각 리프 $v$에는 최대 $C_v$개의 성장판이 있다. 성장판 하나를 완성하려면 모든 계절에서 각각 한 방울씩의 물이 필요하며, 하나의 물방울을 둘 이상의 성장판에 사용할 수는 없다.

리프 $v$가 $t$번째 계절에 $A_{v,t}$개의 물방울을 받았다면, 완성되는 성장판의 수는

이다. 리프 $v$의 성장판 하나가 완성될 때마다 등껍질의 아름다움이 $W_v$만큼 증가한다.

모든 내부 정점의 회전판이 처음 가리킬 통로를 적절히 정하여, 완성된 등껍질의 아름다움 총합의 최댓값을 구하라.

첫 번째 줄에 정점의 수 $N$과 계절의 수 $S$가 공백으로 구분되어 주어진다.

두 번째 줄에 각 계절에 떨어지는 물방울의 수를 나타내는 $S$개의 정수 $X_1, X_2, \ldots, X_S$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 정점의 정보가 $1$번 정점부터 $N$번 정점까지 순서대로 주어진다.

정점 $v$가 $d_v \ge 1$개의 자식을 가지는 내부 정점이라면, 한 줄에 $d_v+1$개의 정수

가 공백으로 구분되어 주어진다. 나열된 순서는 회전판이 회전하는 순서이다.

정점 $v$가 리프라면, 한 줄에 세 정수

가 공백으로 구분되어 주어진다.

입력으로 주어지는 정점과 간선은 $1$번 정점을 루트로 하는 트리를 이룬다. $1$번 정점을 제외한 모든 정점은 정확히 한 번 자식으로 등장한다.

또한 모든 리프 $v$에 대한 $C_vW_v$의 합은 $2^{63}-1$ 이하이다.

완성된 등껍질의 아름다움 총합의 최댓값을 출력한다.

루트인 $1$번 정점에는 자식 통로가 순서대로 $2$번, $3$번, $4$번 정점을 향해 놓여 있다. 각 계절에는 물방울이 두 개씩 떨어진다.

회전판이 처음 $3$번 정점을 가리키도록 정하자. 첫 번째 계절의 두 물방울은 차례대로 $3$번과 $4$번 정점에 도착하고, 회전판은 $2$번 정점을 가리키게 된다. 두 번째 계절의 두 물방울은 차례대로 $2$번과 $3$번 정점에 도착한다.

따라서 두 계절에 모두 물방울을 받은 리프는 $3$번 정점뿐이다. $3$번 정점에서 성장판 하나가 완성되어 아름다움이 $8$만큼 증가한다.

처음에 $2$번 정점을 가리키면 얻는 아름다움은 $5$, $4$번 정점을 가리키면 얻는 아름다움은 $3$이다. 따라서 가능한 최댓값은 $8$이다.