import java.util.*;

class GlasgowDoll extends Cliquer {

    int shallowestSelection; // the lowest indexed vertex that has been selected

    GlasgowDoll (int n,int[][]A,int[] degree,int[] weight,int style) {
	super(n,A,degree,weight,style);
	cpuTime  = System.currentTimeMillis();
	nodes    = 0;
	c        = new long[n];
	adjacent = new int[n][n];

	orderVertices();
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		int u = V[i].index;
		int v = V[j].index;
		adjacent[i][j] = A[u][v];
	    }
	for (int i=0;i<n;i++) weight[i] = V[i].weight;
    }

    void search(){
	ArrayList<Integer> P = new ArrayList<Integer>(n);
	ArrayList<Integer> C = new ArrayList<Integer>(n);
	long pWeight = 0; 
	 for (int i=0;i<n;i++){
	     P.add(i);
	     pWeight = pWeight + weight[i];
	 }
	maxWeight = 0;
	shallowestSelection = n;
	expand(C,P,0,pWeight);
    }	
   
    void expand(ArrayList<Integer> C,ArrayList<Integer> P,long cWeight,long pWeight){	
	nodes++;
	if (pWeight == 0 && cWeight > maxWeight){
	    saveSolution(C,cWeight);
	    for (int i=0;i<=shallowestSelection;i++) c[i] = maxWeight;
	    return;
	}
	if (P.isEmpty()) return;
	if (cWeight + pWeight <= maxWeight) return;
	int v = P.get(0);
	reject(C,P,cWeight,pWeight,v);
	accept(C,P,cWeight,v);
    }

    void accept(ArrayList<Integer> C,ArrayList<Integer> P,long cWeight,int v){
	ArrayList<Integer> newP = new ArrayList<Integer>(P.size());
	long newPweight = 0;
	for (int w : P) 
	    if (adjacent[v][w] == 1){
		newP.add(w);
		newPweight = newPweight + weight[w];
	    }
	ArrayList<Integer> newC = copy(C);
	newC.add(v);
	shallowestSelection = Math.min(shallowestSelection,v);
	if (shallowestSelection != v && cWeight + c[v] <= maxWeight) return;
	expand(newC,newP,cWeight + weight[v],newPweight);
    }
    
    void reject(ArrayList<Integer> C,ArrayList<Integer> P,long cWeight,long pWeight,int v){
	ArrayList<Integer> newP = copy(P);
	newP.remove((Integer) v);
	expand(C,newP,cWeight,pWeight - weight[v]);
    }


    ArrayList<Integer> copy(ArrayList<Integer> L){
	ArrayList<Integer> copy = new ArrayList<Integer>(L.size());
	for (int i : L) copy.add(i);
	return copy;
    }

}