#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

// Esse codigo foi feito rapidamente em uma aula de 
//ctco04 - Analise de Algoritmos, por isso 
//para ser didatico nao esta totalmente otimizado
//para ser feito rapido pode nao seguir todas 
//as boas praticas de programacao.

using namespace std;

int best_sol; //incumbent

//Limitante superior fraco (devolve um valor muito alto)
//Ele considera que todos os itens em [atual, n-1] podem ser
//colocados na mochila (relaxa a restricao de capacidade) 
int limitante_superior1(vector<int> v, vector<int> w, int n, int W, int atual){
  int valor = 0;
  for(int i = atual; i < n; i++){
    valor += v[i];
  }
  return valor;
}

//Limitante superior mais forte. Considera os itens na ordem
//de v[i]/w[i] (os itens precisam estar ordenados dessa forma)
//colocando uma fracao do proximo item
int limitante_superior2(vector<int> v, vector<int> w, int n, int W, int atual){
  double valorLS = 0;
  for(int i = atual; i < n; i++){
    if(w[i] <= W){
      //itemAtual cabe
      valorLS = valorLS + v[i]; 
      W = W - w[i];
    }else{
      //esse item naum cabe, pega soh uma fracao dele
      valorLS = valorLS + ((double) W * ((double) v[i]/w[i]));
      break;
    }
  }
  //Como os itens tem valor inteiro, posso reduzir um pouco esse valor 
  //pegando o piso.
  return floor(valorLS);
}


//algoritmo guloso para o problema da mochila
//considerando os itens entre [atual, n-1]
//precisa receber os itens ordenados por v[i]/w[i]
int greedyKnap(vector<int> v, vector<int> w, int n, int W, int atual){
  int valorPrimal = 0;
  
  for(int i = atual; i < n; i++){
    if(w[i] <= W){
      //itemAtual cabe
      valorPrimal = valorPrimal + v[i]; 
      W = W - w[i];
    }
  }
  
  return valorPrimal;
}

//Devolve o valor da mochila que tem a capacidade residual W, e itens de 
//atual até n-1
int bnb_aux(vector<int> v, vector<int> w, int n, int W, int sol, int atual){
  //atualizando incumbent
  if(sol > best_sol) best_sol = sol;

  if(atual == n){
    return 0;
  }
 
  //calcula um limitante primal, embora esteja certo nao ajudou
  //int primal = sol + greedyKnap(v, w, n, W, atual);
  //if(primal > best_sol) best_sol = primal;
  
  //poda por limitante
  if(sol + limitante_superior2(v, w, n, W, atual) <= best_sol){
    return 0;
  }
  
  int valor_com_atual = -1;
  int valor_sem_atual = -1;
  
  //Poda por inviabilidade
  if(w[atual] <= W){
    //tenta colocar o item atual
    valor_com_atual = v[atual] + bnb_aux(v, w, n, W - w[atual], sol + v[atual], atual + 1);
  }
  
  //tenta sem o item atual
  valor_sem_atual = bnb_aux(v, w, n, W, sol, atual+1);
  
  //devolve a melhor das duas possibilidades
  if(valor_com_atual > valor_sem_atual) return valor_com_atual;
  return valor_sem_atual;
}

int bnb_mochila(vector<int> v, vector<int> w, int n, int W){
  return bnb_aux(v, w, n, W, 0, 0);
}

int main(int argc, char** argv){
	int n;  //Numero de Itens
	int W;  //Capacidade da mochila
	
	//Leitura da instancia
	ifstream instancia;
	instancia.open(argv[1]);
	instancia >> n;
	instancia >> W;

	vector<int> v (n); //Vetor de valores
	vector<int> w (n); //Vetor de pesos

	for (int i = 0 ; i < n ; i++){
		instancia >> v[i];
		instancia >> w[i];
	}

	const time_t begin = clock();


  vector<pair<double, int>> razao(n);

  for(int i = 0; i < n; i++){
    razao[i].first = (double) v[i] / w[i];
    razao[i].second = i;
  }
  
  sort(razao.begin(),razao.end());
  
  vector<int> v_ordenado (n); //Vetor de valores
	vector<int> w_ordenado (n); //Vetor de pesos
  
  for(int i = n-1; i >= 0; i--){
    int itemAtual = razao[i].second;
    v_ordenado[n-(i+1)] = v[itemAtual];
    w_ordenado[n-(i+1)] = w[itemAtual];
  }

  //pega um limitante primal inicial  
  best_sol = greedyKnap(v_ordenado, w_ordenado, n, W, 0);

  //bnb
  int valor_da_mochila = bnb_mochila(v_ordenado, w_ordenado, n, W);

	time_t timeLastSol = clock() - begin;

	cout << best_sol << "\t" << (timeLastSol/double(CLOCKS_PER_SEC))*1000 << endl;
	//cout << n_cortes << endl;

	return 0;
}