다원소 이진 탐색 트리

다중 원소 이진 탐색 트리는 각 노드가 여러 개의 원소를 담을 수 있다는 점에서 보통의 이진 탐색 트리와 다르다. 다만 이진 탐색 트리의 핵심 조건은 일반화된 형태로 그대로 성립한다. 임의의 노드에 대해, 그 노드의 왼쪽 서브트리에 있는 모든 원소는 그 노드가 담고 있는 모든 원소보다 작아야 하고, 오른쪽 서브트리에 있는 모든 원소는 그 노드의 모든 원소보다 커야 한다.

따라서 다중 원소 이진 탐색 트리에서도 보통의 이진 탐색 트리와 똑같은 방식으로 원소를 찾을 수 있다. 각 노드에서 우리는 찾는 원소가 이 노드에 있는지, 아니면 왼쪽 서브트리로 내려가야 하는지 오른쪽 서브트리로 내려가야 하는지를 판단한다. 이 판단 한 번을 연산 한 번으로 셀 때, 어떤 원소를 담고 있는 노드에 도달하는 데 필요한 연산 횟수는 트리의 루트에서 그 노드까지의 레벨 수와 정확히 같다(루트의 레벨을 $1$로 둔다).

노드 메모리 관리의 특성 때문에, 한 노드가 담을 수 있는 원소의 최대 개수는 레벨마다 다르다. 루트의 레벨을 $1$이라 하면, 레벨 $i$의 한 노드가 담을 수 있는 원소의 최대 개수 $m_i$는 주어진 정수 $M$, $K$, $D_j$에 대해 다음과 같이 정의된다.

$m_i = \begin{cases} M & (i = 1) \\ \max\bigl(1,\ m_{i-1} - D_{((i-2) \bmod K) + 1}\bigr) & (i > 1) \end{cases}$

즉 레벨이 하나 깊어질 때마다 빼는 값 $D_j$는 레벨 $2$에서 $D_1$, 레벨 $3$에서 $D_2$, $\ldots$, 레벨 $K+1$에서 $D_K$를 쓰고, 레벨 $K+2$에서 다시 $D_1$로 돌아가는 식으로 순환한다. 예를 들어 $M = 4$, $K = 2$, $D_1 = 1$, $D_2 = 2$이면 루트 노드에는 최대 $m_1 = M = 4$개, 그 직계 자식 노드에는 각각 최대 $m_2 = m_1 - D_1 = 4 - 1 = 3$개, 그 아래 자식 노드에는 각각 $m_3 = m_2 - D_2 = 3 - 2 = 1$개, 그리고 그보다 깊은 모든 레벨에서는 각 노드마다 최대 $m_i = 1$개의 원소를 담을 수 있다.

또한 트리를 사용할 때 서로 다른 원소가 서로 다른 확률로 검색되므로, 균형 잡힌 트리가 항상 평균 검색 시간을 최소로 만들지는 않는다. 예를 들어 가장 작은 원소가 압도적으로 자주 검색된다면 그 원소를 루트 노드에 두는 것이 유리하며, 이 경우 왼쪽 서브트리 전체는 비어 있게 된다.

주어진 원소들의 집합과 각 원소의 검색 확률에 대해, 원소 하나를 검색하는 데 드는 평균 연산 횟수가 최소가 되도록 만든 최적 형태의 다중 원소 이진 탐색 트리에서 그 최소 평균 연산 횟수를 구하여라.

첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다. $N$은 집합의 원소 개수로 $1 \le N \le 100$이고, $1 \le M \le N$, $1 \le K \le N$이다. 이어지는 $K$개의 줄에는 각각 정수 하나가 주어지는데, $j+1$번째 줄의 값이 $D_j$이며 $0 \le D_j \le M$이다. 마지막 줄에는 $N$개의 실수 $P_i$가 주어진다($0 \le P_i \le 1$, $\sum_{i=1}^{N} P_i = 1$). $P_i$는 각 원소가 검색될 확률이며, 원소의 값 순서대로 주어진다(첫 번째 확률이 가장 작은 원소에 대응한다). 원소들의 실제 값은 풀이에 영향을 주지 않으며, 모두 서로 다르다고 가정해도 된다.

최적 형태의 트리에서 검색 한 번에 드는 최소 평균 연산 횟수를 한 줄에 출력한다. 소수점 아래 정확히 $7$자리까지 반올림하여 출력한다.

다음은 두 번째 테스트 케이스에 대한 최적 트리의 모양이다.