408853: GYM103351 C Simplux

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Simpluxtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Batyr is studying math. Some serious math. But as we all know, it sometimes becomes very boring. When it happens, Batyr turns on his imagination and starts wandering in the infinite world of math and programming.

This time, he came up with a very cool linear algebra problem. You are given a matrix $$$a$$$ consisting of $$$m \times n$$$ integers. Also you are given two integer arrays $$$b$$$ of length $$$m$$$ and $$$c$$$ of length $$$n$$$. Your task is to construct a new array $$$x$$$ of length $$$n$$$ such that:

  • Each element $$$x_i$$$ is an integer which satisfies $$$0 \le x_i \le 1$$$;
  • For every $$$i$$$ such that $$$1 \le i \le m$$$ the constraint $$$\sum_{j = 1}^n x_{j} a_{i, j} \equiv b_{i} \pmod{2}$$$ is satisfied;
  • $$$\sum_{i = 1}^n x_{i} c_{i}$$$ is as large as possible.

Print the maximum value of $$$\sum_{i = 1}^n x_{i}c_{i}$$$ you can get and the array $$$x_1, \ldots, x_n$$$ itself.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n,\ m;\ n + m \le 60)$$$.

Each of the next $$$m$$$ lines contains $$$n + 1$$$ integers $$$a_{i, 1}, \ldots, a_{i, n}$$$ and $$$b_i$$$ ($$$0 \le a_{i, j} \le 1$$$, $$$0 \le b_i \le 1$$$).

Next line contains $$$n$$$ integers $$$c_1, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

Output

If it is impossible to construct an array which satisfies the given requirements, print a single integer "-1".

Otherwise, First line of the output should contain a single integer — the maximum value of $$$\sum_{i = 1}^n x_{i}c_{i}$$$.

Second line should contain $$$n$$$ space-separated integers $$$x_1, \ldots, x_n$$$ ($$$0 \le x_i \le 1$$$).

ExamplesInput
2 2
0 1 1
1 0 1
1 1
Output
2
1 1
Input
2 2
0 0 1
1 1 1
1 1
Output
-1
Input
2 2
0 0 0
1 1 1
1 10
Output
10
0 1

加入题单

上一题 下一题 算法标签: