#!/usr/bin/ruby

Planet = Struct.new(:planet_id, :bases, :zerg_forces_avail)
Base = Struct.new(:base_id, :terran, :minerals)
Attack = Struct.new(:base_id,:zerg,:gain)

def min_zerg_required(terran, minerals)
  # when minerals == 1
  #  log(0) throws an error
  # e^(-63s+10)/(e^(-63s+10) + e^(-21z)) >=1
  # e^(-63s+10)>=(e^(-63s+10) + e^(-21z)) 
  # e^(-21z) <=0
  return ((Math.log(minerals-1) + (-63 * terran + 10)) / -21).ceil if minerals != 1
end

def expected_gain(zerg, terran, minerals)
  d = 21*zerg - 63*terran +10
  return 0 if d < 0
  return minerals if d>10
  e = Math.exp(d)
  (minerals * e / (1 + e)).round
end


def opt(list, total)
  return [] if list.empty?
  table = []
  (list.size+1).times { |i| table[i] = [] }
  (0..total).each { |zerg| table[0][zerg] = 0 }
  (1..list.size).each do |base|
    table[base][0] = 0
    (1..total).each do |zerg|
      if list[base-1].zerg <= zerg && (list[base-1].gain + table[base-1][zerg - list[base-1].zerg] > table[base-1][zerg])
        table[base][zerg] = list[base-1].gain + table[base-1][zerg - list[base-1][1]]
      else
        table[base][zerg] = table[base-1][zerg]
      end
    end
  end
  result = []
  i, k = list.size, total
  while i > 0 && k > 0
    if table[i][k] != table[i-1][k]
      result << list[i-1]
      k -= list[i-1].zerg
    end
    i -= 1
  end
  result
end

def cp( a )
  a.inject([[]]){|old,lst|
    new = []
    lst.each{|e| new += old.map{|c| c.dup << e }}
    new
  }
end



filename = ARGV[0]
file = File.open(filename)
# 1 planet -> n basesa
planets= []

# ------------------------------------
# read the file
n_planets = file.readline.to_i

n_planets.times do |p|
 bases = []
  n_bases, zerg_forces_avail  = file.readline.split().collect {|bz| bz.to_i}
  n_bases.times do |b|
    terran_forces, minerals = file.readline.split().collect { |t| t.to_i }
    min_zerg = min_zerg_required(terran_forces,minerals)
    # discard the bases that are not attackable when zerg_forces_avail < min_zerg required
    bases << Base.new(b,terran_forces,minerals) if min_zerg and zerg_forces_avail >= min_zerg 
    end
  planets << Planet.new(p, bases, zerg_forces_avail)
  end
# finish reading the file
# ------------------------------------

planets.each do |p|
 possible = []
  p.bases.each do |b|
 #   puts "#{b.base_id} #{b.terran} #{b.minerals} #{b.min_zerg} " 
    a = []
    zerg  = min_zerg_required(b.terran, b.minerals) 
    previous_gain = nil
    eg = expected_gain(zerg, b.terran, b.minerals)
    a << Attack.new(b.base_id,zerg,eg)
    possible << a
  end
possibles = cp(possible )
 opt_zerg, max_gain, opt_a = nil, nil, nil
  possibles.each do |c|
    c = c.sort_by { |a| [a.zerg, a.gain] } 
    ca = opt(c, p.zerg_forces_avail)
    ca.sort! { |a, b| a.base_id <=> b.base_id }
    sum_zerg = ca.inject(0) { |sum, i| sum += i.zerg }
    sum_gain = ca.inject(0) { |sum, i| sum += i.gain }
    if max_gain.nil? || (sum_gain >= max_gain)
      opt_zerg, max_gain = sum_zerg, sum_gain
      opt_a = ca
    end
  end
  puts "#{opt_zerg} #{max_gain}\n"
  puts opt_a.inject([]) { |a, b| a << b.base_id << b.zerg }.join(' ') << "\n"
end