Alice is starting a new hobby! She has $N$ friends who are stamp-collectors, and she's going to try it too. There are $K$ different types of stamps and the $i^{\text{th}}$ stamp type costs $c_i$. Alice knows each of her friends' collections. She wants to build her collection so that the following odd condition is held for any of her $N$ friends: Between her collection and that friend's collection, there are an odd number of stamp types which appear in exactly one of the two collections. What is the minimum cost of a collection which satisfies Alice's condition? The cost of a collection is the sum of the costs of the stamp types in the collection. Alice's collection must have at least one stamp.

A collection will not contain multiple of a single type of stamp. The collection will either have it or it will not.

Constraints

$1\le N\le 500$
$2\le K\le 500$
$1\le c_i\le 1000000$

Input Specification

The first line contains two space-separated integers, $N$ and $K$.
The second line contains $K$ space-separated integers, $c_1,c_2,\dots ,c_K$.
The next $N$ lines contain $K$ space-separated integers, either 0 or 1. Each line represents the collection of one of Alice's friends. If the $i^{\text{th}}$ number is 0, the $i^{\text{th}}$ stamp type is not in this collection. If the number is 1, the stamp type is in the collection.

Output Specification

Output -1 if it is not possible for Alice to build such a collection. Otherwise, output the minimum cost of such a collection.

Sample Input 1

3 2
2 3
1 0
0 1
1 0

Sample Output 1

5

Explanation for Sample 1

Alice should purchase both stamp types.
Between her first friend and this collection, only stamp type $2$ appears exactly once. So there is one stamp type appearing exactly once, which is odd.
Between her second friend and this collection, only stamp type $1$ appears exactly once. So there is one stamp type appearing exactly once, which is odd.
Between her third friend and this collection, only stamp type $2$ appears exactly once. So there is one stamp type appearing exactly once, which is odd.

Sample Input 2

4 3
1 2 3
1 1 1
1 1 0
1 0 1
0 1 1

Sample Output 2

-1

Explanation for Sample 2

Purchasing only the first stamp type satisfies the condition for the second, third, and fourth friend, but it does not satisfy the condition for the first friend. There is no collection of stamp types which satisfies the condition for all four friends.