@data = '50
5
60,10
100,20
120,30
210,45
10,4
20
8
10,7
4,2
5,9
1,4
7,9
3,7
6,4
3,5
0
'.split("\n")

# @data = readlines

P_CROSS = 0.6
P_MUTATION = 0.01

Item = Struct.new(:value, :weight)

Problem = []

def init(count = 0)
  if @data[0] != '0'
    Problem << {Max_weight: @data[0].to_i, N: @data[1].to_i, Items: Array.new(@data[1].to_i)}
    @data[1].to_i.times do |i|
      Problem[count][:Items][i] = Item.new(*@data[i+2].split(',').map(&:to_i))
    end
#    p Problem[count]
    @data = @data[(@data[1].to_i+2)...@data.length]
    init(count+1)
  end
end

def aoj
  n,w = gets().chomp.split(' ').map(&:to_i)
  @data = []
  @data << w
  @data << n
  n.times do |i|
    @data << gets().chomp.split(' ').join(',')
  end

  Problem << {Max_weight: @data[0], N: @data[1], Items: Array.new(@data[1])}
  @data[1].times do |i|
    Problem[0][:Items][i] = Item.new(*@data[i+2].split(',').map(&:to_i))
  end
end

class GA

  # 0: ??\???????????? 1: ??\?????????
  GENE = Struct.new(:score, :chromosome)

  def initialize(population, items, max)
    @generation = 1
    @population = population # ????????°
    @items = items
    @max = max # ??????????????????????????§??????
    @size = items.length # ????????????
    @genes = Array.new(@population) { GENE.new(0, Array.new(@items.length)) }
    start_time = Time.now
#    p @items

#    srand(start_time.sec)

    @genes.each do |gene|
      gene.chromosome.map! { |locas| locas = rand(2) }
#      puts gene
    end

    evaluate(@genes)

    sort_genes
#   puts @genes

  end

  def evaluate(genes)
    genes.each do |gene|
      value_sum = 0
      weight_sum = 0
      gene.chromosome.each_with_index do |locas, index|
        if locas == 1
          value_sum += @items[index].value
          weight_sum += @items[index].weight
        end
      end
      if weight_sum <= @max && weight_sum != 0
        gene.score = value_sum
      else
        gene.score = 1
      end
    end
#   puts genes
  end

  def sort_genes
    @genes.sort_by! { |gene| -gene.score }
  end


  def start
    prev = 0
    end_count = 0
    loop do
      yield(@generation, @genes[0, @population], @genes[0], avg)
      selection
      mutation

      evaluate(@genes)
      sort_genes
#      puts @genes

      if prev == @genes[0].score && prev != 1
        break if end_count > 100
        end_count += 1
      else
        end_count = 0
      end
      prev = @genes[0].score
      @generation += 1
    end

    value_sum = 0
    weight_sum = 0
    @genes[0].chromosome.each_with_index do |locas, index|
        if locas == 1
          value_sum += @items[index].value
          weight_sum += @items[index].weight
        end
    end
#    puts "value_sum : " + value_sum.to_s
    puts value_sum.to_s
#    puts "weight_sum : " + weight_sum.to_s


    yield(@generation, @genes[0,@population], @genes[0], avg)
  end


  def selection
    # ??¨???????????????
    # ??¨??????????????????????????????????????????
    # http://mikilab.doshisha.ac.jp/dia/research/person/jiro/reports/GAparams/GAparams03.html
    # ??????????????????????????????????????¶?????°?????????"??????????????????
    # ?¬?????????£??§?????????????????????????????°???????????????

    # ??¨????????????????????????????????????????????? ???
    #    @genes.first.chromosome = @parents.first.chromosome

    #    @parents = Marshal.load(Marshal.dump(@genes))
    @parents = Array.new(@population)
    @elite = Marshal.load(Marshal.dump(@genes.first))
    @parents[0] = @elite

#    p @genes

    linear_scaling

    # ????????¬????????????
    #    1.upto((@size)/2) do |i|
    # ??????????????????????????????????????¬?????????????????????
#    p sum
#    p @genes
    1.upto(@population-1) do |i|
      @parents[i] = Marshal.load(Marshal.dump(@genes[roulette(rand(sum))]))
#      crossover(roulette,roulette,@size-(i*2-1),@size-(i*2))
    end

    @genes = []

    # ????????????????????????????????????,?¬?????????£????????????????????? ? ???????????????????????????????????§?????¶ => N ~ 2N ???????
    #    count = 0
    @population.times do |i|
      @population.times do |j|
        if rand < P_CROSS
          crossover(i, j) #, count, count+1)
#          count += 2
#          break if count > @population
          break
        else
          @genes << @parents[i]
          break
        end
      end
    end

  end


  # ?????¢?????±???????????°
  # ????????? fi ??? f'i ??????????????????
  # a = 1 , b = (fN - f1*N) / N -1  =>  f'i = a * fi + b
  def linear_scaling
    f_avg = avg
    f_max = @genes[0].score
    f_min = @genes[-1].score
#    p f_avg, f_min

    return if f_avg == f_min

    a = 0
    b = 0
    c = 2.0
    n = @parents.length

#    p f_min >= (c * f_avg - f_max)/(c - 1.0)

    if f_min >= (c * f_avg - f_max)/(c - 1.0)
      a = (c - 1.0) * f_avg / (f_max - f_avg)
      b = f_avg * (f_max - c*f_avg)/(f_max - f_avg)
    else
      a = f_avg / (f_avg - f_min)
      b = -f_min * f_avg / (f_avg - f_min)
    end
    @genes.each { |gene| gene.score = a * gene.score + b }
  end

  def roulette(prob)
#    puts "sum : %d" % sum
    @genes.each_with_index do |gene, index|
      prob -= gene.score
      return index if prob < 0
    end
  end

  # 2?????????
  def crossover(p1, p2) #, c1, c2)
#    p p1, p2
    parent1 = Marshal.load(Marshal.dump(@parents[p1]))
    parent2 = Marshal.load(Marshal.dump(@parents[p2]))

    start_id = rand(@size)
    cross_length = rand(@size - start_id)

    parent1.chromosome[start_id, cross_length], parent2.chromosome[start_id, cross_length] = parent2.chromosome[start_id, cross_length], parent1.chromosome[start_id, cross_length]
    @genes << parent1
    @genes << parent2
#@genes[c1].chromosome = parent1
#@genes[c2].chromosome = parent2
#    evaluate(@genes[-1])
#    evaluate(@genes[-2])
  end

  def mutation
    @genes.each_with_index do |gene, index|
      if rand < P_MUTATION
        i = rand(@size)
        gene.chromosome[i] = (gene.chromosome[i] - 1).abs
      end
    end
  end

  def sum
#    p @genes
#    p @genes.map{|item| item[:score]}
     @genes.map { |item| item[:score] }.inject(:+)
  end

  def avg
    sum / @genes.length
    #sum = @genes.select{|item| item[:score]>1}
    #sum.map{|item| item[:score]}.inject(:+)/sum.length
    #    p sum.inject{|arr,item| arr + item[:score]}#/sum.length
  end

end


if __FILE__ == $0
  aoj
#  init
#  p Problem
#  p Problem[0][:Items][0].weight

  population = 300

  Problem.each do |problem|
    ga = GA.new(population, problem[:Items], problem[:Max_weight])
    ga.start do |generation, genes, max_score, average|
#      puts 'generation : ' + generation.to_s
#      puts 'elite : ' + genes[0].to_s
#      genes.each do |item|
#        p item
#      end
#      break if gets =~ /x/
    end

  end


end