E. Polynomial K Paths
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a directed graph $$$G = (V, E)$$$ with $$$n$$$ vertices and $$$m$$$ edges, where $$$V$$$ is the set of vertices and $$$E$$$ is the set of edges. The vertices are numbered from $$$1$$$ to $$$n$$$. You're also given the coefficients $$$c_0, c_1, \ldots, c_d$$$ of a $$$d$$$ degree polynomial $$$f$$$ described by $$$f(X)=\sum_{i=0}^d c_i X^i$$$.

Your task is to find $$$k$$$ (not necessarily distinct) simple paths from vertex $$$1$$$ to vertex $$$n$$$ such that the following cost is minimized:

  • Suppose the edge $$$e$$$ is used $$$X_e$$$ times across the $$$k$$$ paths. Then the cost incurred is $$$\sum_{e \in E} X_e \cdot f(X_e)$$$.

Output the minimum possible cost if the paths are chosen optimally. It is guaranteed that there exists at least one path from $$$1$$$ to $$$n$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 20$$$) — the number of test cases.

The first line of each test case contains four integers $$$n$$$ ($$$1 \leq n \leq 100$$$), $$$m$$$ ($$$0 \leq m \leq 200$$$), $$$k$$$ ($$$1 \leq k \leq 50$$$), and $$$d$$$ ($$$1 \leq d \leq 6$$$).

The next line contains $$$d + 1$$$ non-negative integers $$$c_0, c_1, \ldots, c_{d}$$$ ($$$0 \leq c_i \leq 50$$$).

The following $$$m$$$ lines contain two integers each: $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), denoting there is a directed edge from vertex $$$u$$$ to vertex $$$v$$$.

It is guaranteed that there are no self-loops and multiple edges in the graph and there is at least one path from vertex $$$1$$$ to vertex $$$n$$$.

Output

For each test case, print the minimum cost if the $$$k$$$ paths are chosen optimally.

Example
Input
1
6 7 4 3
0 1 0 2
1 2
1 3
1 4
1 5
2 6
3 6
4 6
Output
84
Note

Here, the optimal solution is to choose the following $$$4$$$ paths: $$$1 \to 2 \to 6$$$, $$$1 \to 3 \to 6$$$, $$$1 \to 4 \to 6$$$, and $$$1 \to 4 \to 6$$$. Edges $$$(1, 2), (1, 3), (2, 6), (3, 6)$$$ are used $$$1$$$ time each, contributing $$$1 \cdot f(1) + 1 \cdot f(1) + 1 \cdot f(1) + 1 \cdot f(1) = 12$$$ to the total cost. Edges $$$(1, 4)$$$ and $$$(4, 6)$$$ are used 2 times each, contributing $$$2 \cdot f(2) + 2 \cdot f(2) = 72$$$ to the total cost. So the total cost is $$$12 + 72 = 84$$$. It can be proven that you can not achieve a lower cost than $$$84$$$.