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

Difficulty: interview

Starter code:

Solutions:
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()
#print(books)
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(i, j, hor, ver, ans)
print(ans)


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())
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())
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])
# 12 3 15 5 1
ans = float("inf")
for j in range(2 * n + 1):
    if dp[n - 1][j] <= j:
        ans = min(ans, j)
print(ans)

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

'''
Created on Jan 26, 2015

@author: mohamed265
'''
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):
        #print(i+ 2*j, tOne[i] + tTwo[j])
        if i + 2 * j >= tOne[i] + tTwo[j]:
            slon = min(slon, i + 2 * j)
# print(tOne, tTwo)
print(slon)


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)
            return
print(s1)


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)

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())

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))



# Made By Mostafa_Khaled


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))

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())
m = 2*n + 1
res = set([(0, 0)])
for i in range(n):
    t, w = list(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 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


def __starting_point():
    Solution = CodeforcesTask294BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()

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)


n = int(input())
dif=[]
li1=[]
li2=[]
a1=b1=0
#print(lis)
for i in range(n):
    a,b=list(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]
#        print(i,j,s)    
        if i+2*j>=s:
            ans=min(ans,i+2*j)
print(ans)                                



from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
#def print(x): return sys.stdout.write(str(x)+'\n')
#sys.setrecursionlimit(100000)
mod=int(1e9+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
        else:
            if 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())
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))

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=10e18
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)