def knapsack(items, budget)
	table = (0..1).map{ Array.new(budget+1, 0) }
	for i in 0..items.size-1
		c, v = items[i]
		for j in 0..budget
			x = table[0][j]
			y = (j >= c ? table[0][j-c] + v : 0)
			table[1][j] = x > y ? x : y
		end
		table << table.shift
	end
	table[0][-1]
end

loop {
	n = gets.to_i
	break if n == 0
	a = gets.split.map &:to_i
	sum = a.inject(:+)
	p sum - 2 * knapsack(a.zip(a), sum/2)
}