35502번 - 주사위 놀이 스페셜 저지

cubic이 $N \times M$ 크기의 격자판에서 $(1,1)$에서 출발하여 $(N,M)$까지 이동하려 한다.

이동 거리는 주사위를 굴려 정한다. 주사위를 굴렸을 때 각 면이 나올 확률은 모든 면에 대해 동일하다. 주사위를 굴려 나온 눈금만큼 상하좌우 중 한 방향으로 정확히 눈금에 해당하는 칸 수만큼 이동하거나 이동을 포기할 수 있다. 나온 눈금보다 적게 이동하는 것은 허용되지 않으며, 격자판을 벗어나는 이동은 할 수 없다.

cubic이 $(N,M)$에 도달할 수 있다면 도달하기까지 주사위를 굴리는 횟수의 기댓값을 최소로 하는 전략을 취했을 때, 그 기댓값을 구해보자.

첫 번째 줄에 격자판의 크기 $N, M$과 주사위의 면의 개수 $D$가 주어진다.

두 번째 줄에 각 주사위 면에 적힌 눈금의 개수 $A_1, A_2, \cdots, A_D$가 공백으로 구분되어 주어진다.

첫 번째 줄에 cubic이 $(N,M)$에 도달할 수 있다면, 최적의 전략을 취했을 때 주사위를 굴리는 횟수의 기댓값을 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

도달할 수 없다면 -1을 출력한다.

• $1\le N\le 500$
• $1\le M\le 500$
• $2\le D\le 6$
• $1\le i\le D$
• $1\le A_i\le 499$