A fleet of ~K~ identical trucks having capacity ~Q~ need to be scheduled to delivery pepsi packages from a central depot ~0~ to clients ~1, 2, . . . , n~. Each client ~i~ requests ~d[i]~ packages. The distance from location ~i~ to location ~j~ is ~c[i, j],~ ~0 ≤ i, j ≤ n~. A delivery solution is a set of routes: each truck is associated with a route, starting from depot, visiting some clients and returning to the depot for deliverying requested pepsi packages such that:

• Each client is visited exactly by one route
• Total number of packages requested by clients of each truck cannot exceed its capacity
• Each truck must visit at least one client

Goal: Find a solution having minimal total travel distance

Note that: the orders of clients in a route is important, e.g., routes ~0 \to 1 \to 2 \to 3 \to 0~ and ~0 \to 3 \to 2 \to 1 \to 0~ are different.

Dữ liệu vào

• Line ~1~: ~n, K, Q~ ~(2 ≤ n ≤ 10, 1 ≤ K ≤ 5, 1 ≤ Q ≤ 20)~
• Line ~2~: ~d[1], ..., d[n]~ ~(1 ≤ d[i] ≤ min(Q, 10))~
• Line ~i + 3~: the ~i^{th}~ row of the distance matrix ~c(i = 0, . . . , n)~ ~(0 \leq c[i, j] \leq 10^9)~

Dữ liệu ra

Minimal total travel distance.

Sample Input

4 2 15
7 7 11 2
0 12 12 11 14
14 0 11 14 14
14 10 0 11 12
10 14 12 0 13
10 13 14 11 0

Sample Output

70