Clique Graph Shortest Path Sum

An undirected, unweighted, connected graph $G$ has $N$ vertices numbered 0 through $N-1$.

The edges of $G$ are fixed by two arrays, $V$ and $sizes$. $V$ holds vertex numbers, and the same number may appear in it more than once. $sizes$ holds the lengths of the blocks that $V$ is cut into, starting from the front.

Define $S[i]$ as the sum of the first $i$ elements of $sizes$. For example, if $sizes = \{10, 20, 30\}$, then $S[0] = 0$, $S[1] = 10$, $S[2] = 30$ and $S[3] = 60$.

For every $i$ with $0 \le i < K$, take every pair $(j, k)$ that satisfies $S[i] \le j < k < S[i+1]$. Each such pair gives one edge between vertex $V[j]$ and vertex $V[k]$. In other words, the vertices $V[S[i]]$ through $V[S[i+1]-1]$ form a complete graph. $G$ has no other edges.

Given $N$, $V$ and $sizes$, write a program that computes the shortest path length for every pair of two distinct vertices and prints the sum. The graph given in the input is always connected.

The first line contains the number of vertices $N$ ($2 \le N \le 2500$), the size $M$ of $V$ ($1 \le M \le 5000$) and the size $K$ of $sizes$ ($1 \le K \le 2500$), separated by spaces.

The second line contains the $M$ elements of $V$ in order. The third line contains the $K$ elements of $sizes$ in order.

Every element of $V$ is between 0 and $N-1$. Every element of $sizes$ is an integer between 2 and $N$, and their sum is at most $M$. For every $i$ with $0 \le i < K$, the values $V[S[i]], V[S[i]+1], \dots, V[S[i+1]-1]$ are distinct.

Print on the first line the sum of the shortest path lengths over all pairs of two distinct vertices. Each pair is counted once. The value can exceed the range of a 32-bit integer.