def unbounded_knapsack(items, budget)
	table = [0]
	for i in 1..budget
		table[i] = -Float::INFINITY
		items.each{|c, v|
			next if c > i
			x = table[i-c] + v
			table[i] = x if x > table[i]
		}
	end
	table
end

d = Hash[*%w(^ v < >).zip([[-1, 0], [1, 0], [0, -1], [0, 1]]).flatten(1)]

ns = []
loop {
	n = gets.to_i
	break if n == 0
	ns << n
}

table = unbounded_knapsack([
	[200, -380],
	[300, -550],
	[500, -850],
	[1000, -1520],
	[1200, -1870],
	[1500, -2244]
	],ns.max)

ns.each{|n| p -table[n]}