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.

Input 1

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

Output 1

70