Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is t_{i} and its pages' width is equal to w_{i}. The thickness of each book is either 1 or 2. All books have the same page heights. $1$ 

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure. [Image] 

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.


-----Input-----

The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers t_{i} and w_{i} denoting the thickness and width of the i-th book correspondingly, (1 ≤ t_{i} ≤ 2, 1 ≤ w_{i} ≤ 100).


-----Output-----

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.


-----Examples-----
Input
5
1 12
1 3
2 15
2 5
2 1

Output
5

Input
3
1 10
2 1
2 4

Output
3

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
n = int(input())
(t, w) = ([], [])
for i in range(n):
	(a, b) = map(int, input().split())
	t.append(a)
	w.append(b)
d = [[float('-inf')] * (2 * n + 1) for i in range(n + 1)]
d[0][0] = 0
for i in range(n):
	for j in range(2 * n + 1):
		if j + t[i] <= 2 * n:
			d[i + 1][j + t[i]] = max(d[i + 1][j + t[i]], d[i][j] + w[i])
		d[i + 1][j] = max(d[i + 1][j], d[i][j])
for j in range(2 * n + 1):
	if sum(w) - d[n][j] <= j:
		print(j)
		return


n = int(input())
t = []
for i in range(n):
	e = list(map(int, input().split()))
	t.append(e)
size = 0
size2 = 0
for i in t:
	size += i[0]
	size2 += i[1]
matrix = [[-1000] * (size + 1) for i in range(n)]
for i in range(n):
	matrix[i][0] = 0
for i in range(n):
	for j in range(1, size + 1):
		if t[i][0] <= j:
			if t[i][0] == j and matrix[i - 1][j] == 1000:
				matrix[i][j] = t[i][1]
			else:
				matrix[i][j] = max(matrix[i - 1][j], matrix[i - 1][j - t[i][0]] + t[i][1])
		else:
			matrix[i][j] = matrix[i - 1][j]
for i in range(1, size + 1):
	if i >= size2 - matrix[-1][i]:
		print(i)
		break


n = int(input())
m = 2 * n + 1
pos = set([(0, 0)])
for i in range(n):
	(t, w) = list(map(int, input().split(' ')))
	next_pos = set()
	for (a, b) in pos:
		if a + t <= m:
			next_pos.add((a + t, b))
		if b + w <= m:
			next_pos.add((a, b + w))
	pos = next_pos
print(min((t for (t, w) in pos if t >= w)))


n = int(input())
a = list((tuple(map(int, input().split())) for i in range(n)))
s = sum((t for (t, w) in a))
a = [(t / w, t, t + w) for (t, w) in a]
a.sort(reverse=True)
(d, i) = (s, 0)
while d >= 0:
	s -= a[i][1]
	d -= a[i][2]
	i += 1
i -= 1
s += a[i][1]
d += a[i][2]
if a[i][1] == 2:
	j = i + 1
	while j < n and a[j][1] == 2:
		j += 1
	if j < n and d >= a[j][2]:
		i = 0
		s -= 1
if i > 0:
	i -= 1
	if a[i][1] == 1:
		d += a[i][2]
		j = i + 1
		while j < n and a[j][1] == 1:
			j += 1
		if j < n and d >= a[j][2]:
			s -= 1
print(s)


n = int(input())
dif = []
li1 = []
li2 = []
a1 = b1 = 0
for i in range(n):
	(a, b) = map(int, input().split())
	if a == 1:
		li1.append(b)
	else:
		li2.append(b)
li1.sort(reverse=True)
li2.sort(reverse=True)
l1 = len(li1)
l2 = len(li2)
ans = 10000000000
for i in range(l1 + 1):
	for j in range(l2 + 1):
		s = 0
		for k in range(i, l1):
			s += li1[k]
		for k in range(j, l2):
			s += li2[k]
		if i + 2 * j >= s:
			ans = min(ans, i + 2 * j)
print(ans)


n = int(input())
m = 2 * n + 1
res = set([(0, 0)])
for i in range(n):
	(t, w) = map(int, input().split())
	nxt = set()
	for (a, b) in res:
		if a + t <= m:
			nxt.add((a + t, b))
		if b + w <= m:
			nxt.add((a, b + w))
	res = nxt
print(min((t for (t, w) in res if t >= w)))


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
n = int(data())
dp1 = []
dp2 = []
for i in range(n):
	(t, w) = mdata()
	if t == 1:
		dp1.append(w)
	else:
		dp2.append(w)
dp1.sort(reverse=True)
dp2.sort(reverse=True)
s = len(dp1) + 2 * len(dp2)
k = 0
flag = True
while flag:
	flag = False
	if len(dp2) > 0:
		if len(dp1) > 1:
			m = min(dp1[-1] + dp1[-2], dp2[-1])
			if k + m <= s - 2:
				if m == dp2[-1]:
					dp2.pop()
					k += m
					s -= 2
				else:
					k += dp1.pop()
					s -= 1
				flag = True
		elif len(dp2) > 0 and dp2[-1] + k <= s - 2:
			k += dp2.pop()
			s -= 2
			flag = True
	if flag == False:
		if len(dp1) > 0 and dp1[-1] + k <= s - 1:
			k += dp1.pop()
			s -= 1
			flag = True
print(s)


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
s1 = sum([x[0] for x in a])
a.sort(key=lambda x: x[1] / x[0])
ans = 10 ** 9
s2 = 0
l = -1
for i in range(n):
	if s2 + a[i][1] <= s1 - a[i][0]:
		s2 += a[i][1]
		s1 -= a[i][0]
		l = i
if l != -1 and a[l][0] == 1:
	for i in range(l + 1, n):
		if a[i][0] == 2 and s2 - a[l][1] + a[i][1] <= s1 - 1:
			print(s1 - 1)
			exit(0)
print(s1)


n = int(input())
t1 = []
t2 = []
for _ in range(n):
	(t, w) = map(int, input().split())
	if t == 1:
		t1.append(w)
	else:
		t2.append(w)
t1.sort()
t2.sort()
n1 = len(t1)
n2 = len(t2)
p1 = [0]
p2 = [0]
for i in range(n1):
	p1.append(p1[-1] + t1[i])
for i in range(n2):
	p2.append(t2[i] + p2[-1])
ans = 1
while True:
	am = False
	b = 0
	while 2 * b <= ans:
		a = ans - 2 * b
		if a <= n1 and b <= n2:
			if p1[n1 - a] + p2[n2 - b] <= ans:
				am = True
				break
		b += 1
	if am:
		print(ans)
		break
	ans += 1


3
n = int(input())
books = [[], []]
for _ in range(n):
	(t, w) = tuple(map(int, input().split()))
	books[t - 1].append(w)
for _ in range(2):
	books[_].sort()
ans = 10 ** 9
for i in range(len(books[0]) + 1):
	for j in range(len(books[1]) + 1):
		hor = sum(books[0][:i]) + sum(books[1][:j])
		ver = len(books[0]) - i + 2 * (len(books[1]) - j)
		if hor <= ver and ver < ans:
			ans = ver
print(ans)


n = int(input())
t = [0] * n
w = [0] * n
for i in range(n):
	(t[i], w[i]) = map(int, input().split())
dp = [[float('inf')] * (2 * n + 1) for i in range(n)]
dp[0][t[0]] = 0
dp[0][0] = w[0]
for i in range(n - 1):
	for j in range(2 * n + 1):
		a = dp[i][j]
		if a != float('inf'):
			dp[i + 1][j + t[i + 1]] = min(dp[i + 1][j + t[i + 1]], dp[i][j])
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + w[i + 1])
ans = float('inf')
for j in range(2 * n + 1):
	if dp[n - 1][j] <= j:
		ans = min(ans, j)
print(ans)


import traceback
import math
from collections import defaultdict
from functools import lru_cache
from itertools import accumulate
inf = float('inf')

def main():
	N = int(input())
	(a, b) = ([], [])
	for _ in range(N):
		(t, w) = map(int, input().split())
		if t == 1:
			a.append(w)
		else:
			b.append(w)
	ans = inf
	a.sort(reverse=True)
	b.sort(reverse=True)
	tot = sum(a) + sum(b)
	(a, b) = (accumulate(a), accumulate(b))
	(a, b) = ([0] + list(a), [0] + list(b))
	for (i, x) in enumerate(b):
		for (j, y) in enumerate(a):
			if tot - (x + y) <= i * 2 + j:
				ans = min(ans, i * 2 + j)
	return ans
try:
	ans = main()
	print(ans)
except Exception as e:
	traceback.print_exc()


3
n = int(input())
t = []
w = []
(n1, n2) = (0, 0)
for i in range(n):
	(x, y) = list(map(int, input().split()))
	t.append(x)
	w.append(y)
	n1 += x == 1
	n2 += x == 2
w1 = []
w2 = []
for i in range(n):
	if t[i] == 1:
		w1.append(w[i])
	else:
		w2.append(w[i])
w1.sort(reverse=True)
w2.sort(reverse=True)
ans = 201
for i in range(201):
	for j in range(min(i // 2, n2) + 1):
		k = min(n1, i - 2 * j)
		thickness = 2 * j + k
		if thickness >= sum(w1[k:]) + sum(w2[j:]):
			ans = min(ans, thickness)
print(ans)


import os
from sys import stdin, stdout

def solve(tc):
	n = int(stdin.readline().strip())
	tsum = 0
	wsum = 0
	books = []
	for i in range(n):
		books.append(list(map(int, stdin.readline().split())))
		tsum += books[-1][0]
		wsum += books[-1][1]
	dp = [int(1000000000.0) for i in range(tsum + 1)]
	dp[0] = wsum
	for i in range(n):
		(p, q) = books[i]
		for j in range(tsum, p - 1, -1):
			dp[j] = min(dp[j], dp[j - p] - q)
	for i in range(tsum + 1):
		if dp[i] <= i:
			print(i)
			return
tcs = 1
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


n = int(input())
lis = []
for _ in range(n):
	(tt, ww) = [int(x) for x in input().split()]
	lis.append((tt, -ww))
lis.sort()
(sum1, sum2) = ([0], [0])
for i in range(n):
	if lis[i][0] == 1:
		sum1.append(sum1[-1] - lis[i][1])
	else:
		sum2.append(sum2[-1] - lis[i][1])
ans = 1000000000
(k1, k2) = (len(sum1) - 1, len(sum2) - 1)
v = k2 + 1
for u in range(0, k1 + 1):
	while v - 1 >= 0 and 2 * (v - 1) + sum2[v - 1] >= sum1[k1] + sum2[k2] - sum1[u] - u:
		v -= 1
	if v <= k2:
		ans = min(ans, u + 2 * v)
print(ans)


n = int(input())
(width, thickness) = ([], [])
(one, two) = ([], [])
for _ in range(n):
	(ti, wi) = map(int, input().split())
	(thickness.append(ti), width.append(wi))
	if ti == 1:
		one.append(wi)
	if ti == 2:
		two.append(wi)
(one.sort(), two.sort())
one = [0] + one
two = [0] + two
for i in range(1, len(one)):
	one[i] = one[i - 1] + one[i]
for i in range(1, len(two)):
	two[i] = two[i - 1] + two[i]
ans = 1e+19
for i in range(len(one)):
	for ii in range(len(two)):
		thick = i + 2 * ii
		width = one[len(one) - i - 1]
		width += two[len(two) - ii - 1]
		if width <= thick:
			ans = min(ans, thick)
print(ans)


R = lambda : map(int, input().split())
n = int(input())
unset = -1000000
bs = [[0, 0]] + [list(R()) for i in range(n)]
dp = [[unset] * 201 for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(201):
		(t, w) = (bs[i + 1][0], bs[i + 1][1])
		if dp[i][j] != unset:
			dp[i + 1][j + t] = max(dp[i + 1][j + t], dp[i][j] + t)
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - w)
for i in range(201):
	if dp[n][i] >= 0:
		print(i)
		break


n = int(input())
tOne = [0]
tTwo = [0]
sizeOne = 1
sizetwo = 1
slon = 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
for i in range(n):
	t = input().split()
	if t[0] == '1':
		tOne.append(int(t[1]))
		sizeOne += 1
	else:
		tTwo.append(int(t[1]))
		sizetwo += 1
tOne.sort(reverse=False)
tTwo.sort(reverse=False)
for i in range(1, sizeOne):
	tOne[i] += tOne[i - 1]
for i in range(1, sizetwo):
	tTwo[i] += tTwo[i - 1]
tOne.reverse()
tTwo.reverse()
for i in range(sizeOne):
	for j in range(sizetwo):
		if i + 2 * j >= tOne[i] + tTwo[j]:
			slon = min(slon, i + 2 * j)
print(slon)


from operator import itemgetter

class CodeforcesTask294BSolution:

	def __init__(self):
		self.result = ''
		self.books_count = 0
		self.books_dims = []

	def read_input(self):
		self.books_count = int(input())
		for x in range(self.books_count):
			self.books_dims.append([int(y) for y in input().split(' ')])

	def process_task(self):
		v1 = sum([1 for x in self.books_dims if x[0] == 1])
		v2 = sum([1 for x in self.books_dims if x[0] == 2])
		v1_books = [x[1] for x in self.books_dims if x[0] == 1]
		v2_books = [x[1] for x in self.books_dims if x[0] == 2]
		v1_books.sort()
		v2_books.sort()
		minimum = v1 + v2 * 2
		for x in range(v1 + 1):
			for y in range(v2 + 1):
				width = x + y * 2
				thickness = sum(v1_books[:v1 - x]) + sum(v2_books[:v2 - y])
				if thickness <= width:
					minimum = min(minimum, width)
		self.result = str(minimum)

	def get_result(self):
		return self.result
Solution = CodeforcesTask294BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


one = []
two = []
x = int(input())
for i in range(x):
	(a, b) = list(map(int, input().split(' ')))
	if a == 1:
		one.append(b)
	else:
		two.append(b)
one.sort()
two.sort()
minx = 9000000
for ones in range(0, len(one) + 1):
	for twos in range(0, len(two) + 1):
		w = ones + 2 * twos
		a = sum(one[:len(one) - ones]) + sum(two[:len(two) - twos])
		if a <= w:
			minx = min(minx, w)
print(minx)