3SAT问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


对于给定的带权3-CNF,设计一个蒙特卡罗算法,使其权值之和尽可能大。

Input

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

Output

将计算出的最大权值输出。

Sample Input

5 3
9 3 1 4 0
9 1 -5 3 0
8 2 -5 1 0

Sample Output

26

Hint

 

Source