Problem ID:
dtqg_cvrpopt

Points:
3.7 (partial)

Time limit:
1.0s

Memory limit:
1G

Input:
stdin

Output:
stdout

Author:

Problem types

Allowed languages

C, C++, ~~Golang~~, Java, Pascal, Perl, Python, Rust

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.

#### Input

- 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)~

#### Output

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
```

## Comments