可满足问题的近似算法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


设计并实现上述近似算法。

Input

输入数据的第一行有2个正整数k和m,分别表示变量数和布尔表达式数。接下来的m 行中,每行有若干个整数i,j,k,…,0,表示表达式含的变量下标分别为i,j,k,…,行末以0 结尾。下标为负数时,表示相应的变量为取反变量。

Output

将计算出的最大可满足合取式数输出。

Sample Input

5 3
3 1 4 0
1 -5 3 0
2 -5 1 0

Sample Output

3

Hint

 

Source