import java.io.*;
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
import org.chocosolver.solver.*;
import org.chocosolver.solver.variables.*;
import org.chocosolver.solver.constraints.*;
import org.chocosolver.solver.search.strategy.*;

public class MWCCP {

    int n;               // number of vertices
    int[] weight;        // vertex weights
    Solver solver;       // a solver object, to attach variables and constraints
    int[][] adjacent;    // adjacent[i][j] = 1 <-> vertices are adjacent
    int[] degree;        // vertex degree;
    IntVar[] vertex;     // vertex[i] = 1 <-> ith vertex selected
    String id;           // an identification for the problem
    IntVar totalWeight;  // sum of weights of selected vertices
    int minWeight;       // minimum vertex weight
    int maxWeight;       // maximum vertex weight
    String order;        // increasing ("incWeight" or "incDegree") or decreasing ("decWeight" or decDegree")
	
    public MWCCP(String fname,String order) throws Exception {
	Scanner sc     = new Scanner(new File(fname));
	id             = fname;
	solver         = new Solver(id);
	n              = sc.nextInt();
	minWeight      = sc.nextInt();
	maxWeight      = sc.nextInt();
	weight         = new int[n];
	adjacent       = new int[n][n];
	degree         = new int[n];
	vertex         = VF.enumeratedArray("vertex",n,0,1,solver);
	totalWeight    = VF.enumerated("totalWeight",minWeight,maxWeight*n,solver); // dumb
	this.order     = order;

	// read vertex weights
	for (int i=0;i<n;i++){
	    sc.nextInt(); // skip vertex id
	    weight[i] = sc.nextInt();
	}

	// read edges
	while(sc.hasNext()){
	    int u = sc.nextInt();
	    int v = sc.nextInt();
	    adjacent[u][v] = adjacent[v][u] = 1;
	    degree[u]++;
	    degree[v]++;
	}

	sc.close();

	// non-adjacent vertice cannot be in clique together
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++)
		if (adjacent[i][j] == 0) solver.post(ICF.arithm(vertex[i],"+",vertex[j],"<",2));

	// weight of clique is scalar vertices with weights
	solver.post(ICF.scalar(vertex,weight,totalWeight));
    }

    // dumb swap for use with bubbleSort (please, tell no one)
    void swap(int i,int j,int[] property,IntVar[] vertex){
	int temp      = property[i];
	IntVar tempIV = vertex[i];
	property[i]   = property[j];
	vertex[i]     = vertex[j];
	property[j]   = temp;
	vertex[j]     = tempIV;
    }

    // get decision variables, sorted increasing or decreasing
    // on weight or degree. NOTE: if "illegal" order then not sorted (a bug/feature)
    IntVar[] getDecisionVars(String order){
	IntVar[] sortedVertex = new IntVar[n];
	int[] sortedWeight = new int[n];
	int[] sortedDegree = new int[n];
	for (int i=0;i<n;i++){
	    sortedVertex[i] = vertex[i];
	    sortedWeight[i] = weight[i];
	    sortedDegree[i] = degree[i];
	}
	for (int i=n-1;i>0;i--)
	    for (int j=0;j<i;j++)
		if ((order.equals("decWeight") && sortedWeight[j] < sortedWeight[j+1]) ||
		    (order.equals("incWeight") && sortedWeight[j] > sortedWeight[j+1]))
		    swap(j,j+1,sortedWeight,sortedVertex);
		else if ((order.equals("decDegree") && sortedDegree[j] < sortedDegree[j+1]) ||
			 (order.equals("incDegree") && sortedDegree[j] > sortedDegree[j+1]))
		    swap(j,j+1,sortedDegree,sortedVertex);
	return sortedVertex;
    }

    public void optimize(){
	solver.set(ISF.lexico_UB(getDecisionVars(order)));
	solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE,totalWeight);
    }


    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
	String order = "none";
	if (args.length == 2) order = args[1];
	MWCCP mwc = new MWCCP(args[0],order);
	mwc.optimize();
	Solver solver = mwc.solver;
	System.out.print(mwc.totalWeight.getValue() + " ");
	System.out.print(solver.getMeasures().getNodeCount() + " ");
	System.out.println((int)(solver.getMeasures().getTimeCount() * 1000));
	for (int i=0;i<mwc.n;i++)
	    if (mwc.vertex[i].getValue() == 1) System.out.print(i +" ");
	System.out.println();
    }
}
//
// Anecdotal Evidence
// ------------------
// It appears that when there is a large variation in proportion of weights, e.g. 1 <= weight <= 10,
// sorting vertices by decreasing weight is a winner (and this is like bin packing heuristic)
// When there is a low variation in proportion of weights, e.g. 1001 <= weight <= 1010,
// sorting vertices by increasing degree is a winner (and this agrees with kappa heuristic for max clique)
//