package xj;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class PaMai { static int T,goods,man; static int data[][]; static int money[]; static int maxmoney; static boolean []Rused; static boolean []Sused;
public static void main(String[] args) throws FileNotFoundException { /* Scanner sc=new Scanner(System.in); */ Scanner sc=new Scanner(new File("src/PaiMai")); T=sc.nextInt(); for (int t = 0; t < T; t++) { goods=sc.nextInt(); man=sc.nextInt(); data=new int [man+1][3]; money=new int [man+1]; Rused=new boolean[man+1]; Sused=new boolean[goods+1]; for (int i = 1; i < man+1; i++) { data[i][0]=sc.nextInt();data[i][1]=sc.nextInt();data[i][2]=sc.nextInt(); money[i]=sc.nextInt(); } dfs(1,0); /*for (int i = 1; i < man+1; i++) { for (int j = 1; j < goods+1; j++) { System.out.print(" "+data[i][j]); } System.out.println(" "+money[i]); }*/ System.out.println(maxmoney); } }
private static void dfs(int step, int sum) { if(step>man){ if(maxmoney<sum){maxmoney=sum;} return; } for (int i = 1; i <=man; i++) { if(!Rused[i]){ //全买 if(!Sused[data[i][0]]&&!Sused[data[i][1]]&&!Sused[data[i][2]]){ sum+=money[i]*3; Sused[data[i][0]]=true; Sused[data[i][1]]=true; Sused[data[i][2]]=true; dfs(step+1,sum); sum-=money[i]*3; Sused[data[i][0]]=false; Sused[data[i][1]]=false; Sused[data[i][2]]=false; } //不买 dfs(step+1,sum); //买两件 if(!Sused[data[i][0]]&&!Sused[data[i][1]]){ sum+=money[i]*2; Sused[data[i][0]]=true; Sused[data[i][1]]=true; dfs(step+1,sum); sum-=money[i]*2; Sused[data[i][0]]=false; Sused[data[i][1]]=false; } if(!Sused[data[i][1]]&&!Sused[data[i][2]]){ sum+=money[i]*2; Sused[data[i][1]]=true; Sused[data[i][2]]=true; dfs(step+1,sum); sum-=money[i]*2; Sused[data[i][1]]=false; Sused[data[i][2]]=false; } if(!Sused[data[i][0]]&&!Sused[data[i][2]]){ sum+=money[i]*2; Sused[data[i][0]]=true; Sused[data[i][2]]=true; dfs(step+1,sum); sum-=money[i]*2; Sused[data[i][0]]=false; Sused[data[i][2]]=false; } } } }
}
//
2 5 3 1 2 3 50 2 4 5 90 1 3 4 70 12 4 1 2 3 50 4 5 6 70 7 8 9 60 10 11 12 90
//
410 810
