Problem Made Because Delivery Fees Were Too High

Time limit3sMemory limit1024 MB

Summary

Assign N students to M restaurants so each student's equal share of the fee stays within their limit, minimizing the total fee.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

Students at Korea Science Academy often order food for delivery on weekends. Delivery fees have risen sharply, so more students order together.

Each of $N$ students chooses exactly one of $M$ restaurants and places an order there. Students who pick the same restaurant can share the order and split its delivery fee equally. If the $j$ -th restaurant is ordered from, a delivery fee of $c_j$ is charged, and the students who ordered from that restaurant split this fee equally. The fee each student pays does not have to be an integer. The $i$ -th student can order from the $j$ -th restaurant only if the fee that student would pay there is at most $r_{i,j}$ .

Doyoung wants to decide which restaurant each student orders from so that the total delivery fees paid by all students is minimized. Find the minimum possible total.

Input

The first line contains two integers $N$ and $M$ , separated by a space.

The second line contains $M$ integers $c_1, c_2, \cdots, c_M$ , separated by spaces.

The next $N$ lines contain $r_{i,j}$ . The $i$ -th of these lines contains $M$ integers $r_{i,1}, r_{i,2}, \cdots, r_{i,M}$ , separated by spaces.

Output

Print the minimum possible total of delivery fees. If it is impossible for every student to place an order, print -1 instead.

Constraints

$1 \leq N \leq 15$
$1 \leq M \leq 1000$
$1 \leq c_j \leq 10^7$
$0 \leq r_{i,j} \leq 10^7$

Examples3

Example 1
Input
```
3 3
3 2 10
2 0 4
2 0 4
0 2 4
```
Expected output
```
5
```
Example 2
Input
```
3 3
3 2 10
2 0 4
1 0 4
0 2 4
```
Expected output
```
10
```
Example 3
Input
```
4 2
8 8
3 2
3 2
3 1
0 2
```
Expected output
```
-1
```