#/***********************************************************
#    knapsack.rb -- ナップザックの問題
#***********************************************************/

MAXSIZE = 1000
MAXITEM = 100
maxsofar = []
newitem = []

size = []
price = []


print "ナップザックの大きさ? ";  knapsize = gets.to_i
if (knapsize <= 0 || knapsize > MAXSIZE); exit 1; end
print "品目数? ";  n = gets.to_i
if (n <= 0 || n > MAXITEM); exit 1; end
for i in 0...n
    print "品目 #{i} の大きさ? ";  size[i] = gets.to_i
    print "品目 #{i} の価格  ? ";  price[i] = gets.to_i
end

smallest = knapsize + 1
for i in 0...n
    if (size[i] < smallest); smallest = size[i]; end
end
for s in 0..knapsize; maxsofar[s] = 0; end
for i in 0...n
    for s in size[i]..knapsize
        space = s - size[i]
        newvalue = maxsofar[space] + price[i]
        if (newvalue > maxsofar[s]) 
            maxsofar[s] = newvalue;  newitem[s] = i
        end
    end
end

print "品目  価格\n"
s = knapsize; while(s >= smallest)
    printf("%4d %5d\n", newitem[s], price[newitem[s]])
    s -= size[newitem[s]]
end
printf("合計 %5d\n", maxsofar[knapsize])

exit 0