import java.io.*;
import java.util.*;
import java.util.Arrays;
import org.chocosolver.util.tools.ArrayUtils;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.constraints.IIntConstraintFactory.*;
//import org.chocosolver.solver.constraints.Constraint;
import org.chocosolver.solver.search.strategy.Search;

public class Allocate {

    Person person[];       // the employees to be allocated to cost centres
    int salary[];          // salary[i] of ith person
    Model model;           // the model
    Solver solver;         // the solver object
    IntVar inCentre[][];   // inCentre[i][j] = 1 iff jth person works in ith cost centre
    IntVar centreSalary[]; // centreSalaries[i] is sum of the salaries in the ith cost centre
    int budget;            // the budget for each cost centre
    int n;                 // number of employees
    int m;                 // number of cost centres
    String id;             // an identification for the problem
	
    public Allocate(String fname,int numberOfPeople,int numberOfCostCentres,int budget) throws Exception {
	n            = numberOfPeople;
	m            = numberOfCostCentres;
	this.budget  = budget;
	id           = fname;
	person       = new Person[n];
	salary       = new int[n];
	model        = new Model(id);
	solver       = model.getSolver();
	inCentre     = model.intVarMatrix("inCentre",m,n,0,1);
	centreSalary = model.intVarArray("centre salaries",m,0,budget);

	Scanner sc = new Scanner(new File(fname));
	for (int i=0;i<n;i++) person[i] = new Person(sc.next(),sc.nextInt());
	sc.close();

	// EDIT
	Arrays.sort(person);
	//
	// first fit decreasing
	//

	for (int i=0;i<n;i++) salary[i] = person[i].salary;

	for (int i=0;i<m;i++)
	    model.scalar(inCentre[i],salary,"=",centreSalary[i]).post();
	// 
	// constrain centreSalary[i] to be the scalar product of inCentre[i] and salary[i]
	//


	for (int i=0;i<n;i++)
	    model.sum(ArrayUtils.getColumn(inCentre,i),"=",1).post();
	//
	// constrain a person such that he/she can only be in one cost centre at a time!
	// i.e. the sum of a column of the array inCentre must be equal to 1,
	//      such that a person is in exactly one cost centre
	//

	// EDIT
	//for (int i=0;i<m-1;i++)
	// model.arithm(centreSalary[i],">=",centreSalary[i+1]).post();
	//
	// symmetry breaking consistent with first fit decreasing
	// costliest cost centres have low index
	//

	// EDIT
	for (int centre=0;centre<m-1;centre++)
	  model.lexLessEq(inCentre[centre+1],inCentre[centre]).post();
	//
	// symmetry breaking such that inCentre[i] lex>= inCentre[i+1]
	//
    }
    
    // solve using value ordering over decision variables
    boolean solve(){
	//solver.setSearch(Search.minDomLBSearch(ArrayUtils.flatten(inCentre)));
	solver.setSearch(Search.minDomUBSearch(ArrayUtils.flatten(inCentre)));
	return solver.solve();
    }
    
    public String toString(){
	String s = id + " " + " #employees: " + n + 
	          " #centres: " + m + " budget: " + budget + "\n";
	for (int i=0;i<m;i++){
	    s = s + "centre[" + i + "] ";
	    for (int j=0;j<n;j++)
		s = s + inCentre[i][j].getValue() + " ";
	    s = s + centreSalary[i].getValue() + "\n";
	}
	s = s + "\n";
	for (int centre=0;centre<m;centre++){
	    s = s + "centre-"+ centre +": ";
	    for (int p=0;p<n;p++)
		if (inCentre[centre][p].getValue() == 1) s = s + person[p] +" ";
	    s = s + " ... cost: "+ centreSalary[centre].getValue() +"\n";
	}
	return s;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
	if (args.length == 0){
	    System.out.println("java Allocate fname budget #employees #centres");
	    return;
	}
	String fname          = args[0];
	int budget            = Integer.parseInt(args[1]);
	int numberOfEmployees = Integer.parseInt(args[2]);    
	int numberOfCentres   = Integer.parseInt(args[3]);

	Allocate alloc = new Allocate(fname,numberOfEmployees,numberOfCentres,budget);
	boolean solved = alloc.solve(); 
	System.out.println(solved);
	if (solved) System.out.println(alloc);
	System.out.println("nodes: " + alloc.solver.getMeasures().getNodeCount() +
			   "   cpu: " + alloc.solver.getMeasures().getTimeCount());
    }
}