408853: GYM103351 C Simplux

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.

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$$$).

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$$$).

2 2
0 1 1
1 0 1
1 1

2
1 1

2 2
0 0 1
1 1 1
1 1

-1

2 2
0 0 0
1 1 1
1 10

10
0 1