-----Horndude77

class TruckBed
    def initialize(width,height)
        @width,@height = width,height
        @boxes = {}

        #This list maintains where it is possible to add boxes
        @insertion_points = [(0...width).to_a * height,
(0...height).map{|i| [i]*width}.flatten].transpose
        sort_insertion_points
    end

    def insert(box)
        @insertion_points.each do |pos|
            [box, box.reverse].each do |curr_box|
                if fits_at? curr_box, pos then
                    @boxes[pos] = curr_box
                    (-1).upto(curr_box[0]) do |x|
                        (-1).upto(curr_box[1]) do |y|
                            @insertion_points.delete [x+pos[0],
y+pos[1]]
                        end
                    end
                    sort_insertion_points
                    return true
                end
            end
        end
        false
    end

    #Stable sort: keep relative order
    #This way we control where insertions happen
    def sort_insertion_points
        n = 0
        @insertion_points.sort_by{|x| n+=1; [x[1], n]}
        @insertion_points.sort_by{|x| n+=1; [x[0], n]}
    end

    #See if box fits at pos
    def fits_at?(box, pos)
        box_min = pos
        box_max = [pos[0]+box[0]-1, pos[1]+box[1]-1]
        return false if (box_max[0] >= @width) || (box_max[1] >=
@height)
        #check for box intersections
        @boxes.each do |curr_pos, curr_box|
            curr_box_min = [curr_pos[0]-1, curr_pos[1]-1]
            curr_box_max = [curr_pos[0]+curr_box[0],
curr_pos[1]+curr_box[1]]
            return false if box_min[0] <= curr_box_max[0] && box_max[0]

    def to_s
        bed = Array.new(@width) { Array.new(@height) {'-'} }
        @boxes.each do |pos,box|
            box[0].times do |x|
                box[1].times do |y|
                    bed[x+pos[0]][y+pos[1]] = 'X'
                end
            end
        end
        bed.transpose.reverse.map {|r| r.join }.join("\n")
    end
end

class String
    def to_dims
        split('x').map {|i| i.to_i}
    end
end

truck_bed_dims = ARGF.gets.to_dims
boxes = ARGF.gets.split.map {|box| box.to_dims.sort.reverse}.sort
{|a,b| a[0]*a[1] <=> b[0]*b[1]}

truck_beds = [TruckBed.new(*truck_bed_dims)]

while boxes.size > 0
    box = boxes.pop
    truck_beds.each do |bed|
        if(bed.insert box) then
            box = nil
            break
        end
    end
    if(box) then
        bed = TruckBed.new(*truck_bed_dims)
        bed.insert(box)
        truck_beds << bed
    end
end