Problem:


Problem B: Old Bridges

Long long ago, there was a thief. Looking for treasures, he was running about all over the world. One day, he heard a rumor that there were islands that had large amount of treasures, so he decided to head for there.

Finally he found n islands that had treasures and one island that had nothing. Most of islands had seashore and he can land only on an island which had nothing. He walked around the island and found that there was an old bridge between this island and each of all other n islands.

He tries to visit all islands one by one and pick all the treasures up. Since he is afraid to be stolen, he visits with bringing all treasures that he has picked up. He is a strong man and can bring all the treasures at a time, but the old bridges will break if he cross it with taking certain or more amount of treasures.

Please write a program that judges if he can collect all the treasures and can be back to the island where he land on by properly selecting an order of his visit.

Input

Input consists of several datasets.

The first line of each dataset contains an integer n.
Next n lines represents information of the islands. Each line has two integers, which means the amount of treasures of the island and the maximal amount that he can take when he crosses the bridge to the islands, respectively.

The end of input is represented by a case with n = 0.

Output

For each dataset, if he can collect all the treasures and can be back, print "Yes" Otherwise print "No"

Constraints

1  ≤ n ≤ 25

Sample Input

3
2 3
3 6
1 2
3
2 3
3 5
1 2
0

Output for the Sample Input

Yes
No



Sample input:
3
2 3
3 6
1 2
3
2 3
3 5
1 2
0


Sample output:
Yes
No

Submission status: Wrong Answer

Solution code:
while True:
    n = input()
    if n == 0: break
    info = []
    for i in range(n):
        lu, w = map(int, raw_input().split())
        info.append((w, lu))
    info.sort()
    lu_sum = 0
    flag = True
    for w, lu in info:
        lu_sum += lu
        if lu_sum > w:
            flag = False
    print("YES" if flag else "NO")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    n = int(raw_input())
    island = []
    if n == 0:
        break
    for i in range(n):
        g,b = map(int,raw_input().split())
        island.append((g,b,b-g))
    island = sorted(island,key = lambda x:(x[2],x[0],x[1]))
    
    gem = 0
    for g,b,c in island:
        gem += g
        if b < gem:
            break
    else:
        print 'Yes'
        continue
    print 'No'

Submission status: Wrong Answer

Solution code:
while True:
    n = input()
    if n == 0: break
    info = []
    for i in range(n):
        lu, w = map(int, raw_input().split())
        info.append((w, -lu))
    info.sort()
    lu_sum = 0
    flag = True
    for w, lu in info:
        lu_sum -= lu
        if lu_sum > w:
            flag = False
    print("YES" if flag else "NO")

Submission status: Wrong Answer

Solution code:
while True:
    n = input()
    if n == 0: break
    info = []
    for i in range(n):
        lu, w = map(int, raw_input().split())
        info.append((w, -lu))
    info.sort()
    lu_sum = 0
    flag = True
    for w, lu in info:
        lu_sum -= lu
        if lu_sum > w:
            flag = False
    print "YES" if flag else "NO"

Submission status: Wrong Answer

Solution code:
__author__ = 'admin'

while True:
    count_shima=input()
    if count_shima==0: break

    A = [list(map(int,raw_input().split())) for i in xrange(count_shima)]

    A.sort()

    weight=0
    frg=0
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            print "NO"
            frg=1
            break
    if frg==0:
        print "YES"

Submission status: Wrong Answer

Solution code:
while True:
    count_shima=input()
    if count_shima==0: break

    A = [list(map(int,raw_input().split())) for i in xrange(count_shima)]

    A.sort()

    weight=0
    flag=True
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            flag=False
    print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
while True:
    count_shima=input()
    if count_shima==0: break
    A=[]
    A = [list(map(int,raw_input().split())) for i in xrange(count_shima)]

    A.sort()

    weight=0
    flag=True
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            flag=False
    print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
while True:
    count_shima=input()
    if count_shima==0: break
    A=[]
    A = [list(map(int,raw_input().split())) for i in range(count_shima)]

    A.sort()

    weight=0
    flag=True
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            flag=False
    print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
while True:
    count_shima=input()
    if count_shima==0: break
    A=[]
    A = [map(int,raw_input().split()) for i in range(count_shima)]

    A.sort()

    weight=0
    flag=True
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            flag=False
    print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
while(1):
    n=int(raw_input())
    if n==0: break
    A=[[0,0] for i in range(n)] 
    for i in range(n):
        [a,b]=map(int,raw_input().split())
        A[i]=[a,b]
    A.sort(key= lambda x: x[0])
    s=0
    for i in range(n):
        if s+A[i][0]>A[i][1]:
            print 'No'
            break
        else:
            s+=A[i][0]
    else:
        print 'Yes'

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    cnt = total = 0
    for a, b in z:
        total += a
        if total > b:
            cnt = 1
            break
    print("Yes" if cnt else "No")

Submission status: Wrong Answer

Solution code:
def sky(x):
    return x[1]


while True:
    n = int(input())
    if n == 0:
        break
    
    brimax = 0
    sumz = 0
    for i in range(n):
        inp = list(map(int, input().split()))
        brimax = max(brimax, inp[1])
        sumz += inp[0]
    if brimax < sumz:
        print("No")
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
def sky(x):
    return x[1]


while True:
    n = int(input())
    if n == 0:
        break
    
    arr = [[] for i in range(n)]
    sumh = 0
    for i in range(n):
        arr[i] = list(map(int, input().split()))
        sumh += arr[i][0]
    arr.sort(key=sky, reverse=True)
    res = True
    for e in arr:
        if sumh < e[1]:
            res = False
            break
        sumh -= e[0]
    if res:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
def sky(x):
    return x[1]


while True:
    n = int(input())
    if n == 0:
        break
    
    arr = [[] for i in range(n)]
    sumh = 0
    for i in range(n):
        arr[i] = list(map(int, input().split()))
        sumh += arr[i][0]
    arr.sort(key=sky, reverse=True)
    print(arr)
    res = True
    for e in arr:
        if sumh > e[1]:
            res = False
            break
        sumh -= e[0]
    if res:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
def solve(l):
	have = 0
	for m, w in l:
		have += w
		if m < have:
			return "NO"
	return "YES"
while True:
	n = input()
	if n == 0: break
	l = [tuple(reversed(map(int, raw_input().split()))) for i in xrange(n)]
	l.sort()
	print solve(l)

Submission status: Wrong Answer

Solution code:
while 1:
    n = input()
    if n==0: break
    t = []; s = 0;
    for i in xrange(n):
        w,l = map(int, raw_input().split())
        t.append([l-w,w])
    t.sort()
    for v in t:
        if s>v[0]:
            s = -1; break;
        s += v[1]
    print "Yes" if s!=-1 else "No"

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = int(raw_input())
	if n == 0:
		break
	bridge = [0 for i in range(n)]
	gold = [0 for i in range(n)]
	for i in range(n):
		gold[i], bridge[i] = map(int,raw_input().split(" "))
	dp = {0:0}
	for i in range(n):
		tmp_dp = dict()
		for k,v in dp.iteritems():
			for j in range(n):
				bit = 1 << j
				if (k & bit != 0):
					continue
				if v + gold[j] <= bridge[j]:
					tmp_dp[k|bit] = v + gold[j]
		dp = tmp_dp
	print "Yes" if (2**n - 1) in dp else "No"

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = int(raw_input())
	if n == 0:
		break
	bridge = [0 for i in range(n)]
	gold = [0 for i in range(n)]
	for i in range(n):
		gold[i], bridge[i] = map(int,raw_input().split(" "))
	dp = {0:0}
	for i in range(n):
		tmp_dp = dict()
		for k,v in dp.iteritems():
			for j in range(n):
				bit = 1 << j
				if (k & bit != 0) or (k|bit in tmp_dp):
					continue
				if v + gold[j] <= bridge[j]:
					tmp_dp[k|bit] = v + gold[j]
		dp = tmp_dp
	print "Yes" if (2**n - 1) in dp else "No"

Submission status: Memory Limit Exceeded

Solution code:
def dfs(state, s):
    if s == su: return 1
    if memo[state]: return 0
    memo[state] = 1
    for j, e in enumerate(D):
        if state & (1 << j) == 0 and s+e[0]<=e[1]:
            if dfs(state | (1 << j), s+e[0]):
                return 1
    return 0

while 1:
    n = input()
    if n==0: break
    memo = [0]*2**n
    D = [map(int, raw_input().split()) for i in xrange(n)]
    su = sum(e[0] for e in D)
    print "Yes"*dfs(0, 0)or"No"

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop
def dijkstra():
    que = []
    dist = {}
    heappush(que, (0, 0))
    dist[0] = 0
    while que:
        co, state = heappop(que)
        if dist[state] < co: continue
        if state == goal: return 1
        for i, e in enumerate(D):
            if state & (1 << i) == 0 and co+e[0]<=e[1]:
                n_state = state | (1 << i)
                if n_state not in dist:
                    heappush(que, (co+e[0], n_state))
                    dist[n_state] = co+e[0]
    return 0

while 1:
    n = input()
    if n==0: break
    D = [map(int, raw_input().split()) for i in xrange(n)]
    su = sum(e[0] for e in D)
    goal = 2**n-1
    print "Yes"*dijkstra()or"No"

Submission status: Accepted

Solution code:
# AOJ 1052: Old Bridges
# Python3 2018.7.7 bal4u

while True:
	n = int(input())
	if n == 0: break
	tbl = [list(map(int, input().split())) for i in range(n)]
	tbl.sort(key=lambda x:(x[1],x[0]))
	s, f = 0, True
	for v, w in tbl:
		s += v
		if s > w:
			f = False
			break
	print("Yes" if f else "No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    n = int(raw_input())
    island = []
    if n == 0:
        break
    for i in range(n):
        g,b = map(int,raw_input().split())
        island.append((g,b))
    island = sorted(island,key = lambda x:(x[1],x[0]))
    
    gem = 0
    for g,b in island:
        gem += g
        if b < gem:
            break
    else:
        print 'Yes'
        continue
    print 'No'

Submission status: Accepted

Solution code:
while 1:
	n = int(raw_input())
	if n == 0:
		break
	land = [map(int,raw_input().split(" ")) for i in range(n)]
	land.sort(key = lambda x:(x[1],x[0]))
	gold = 0
	for i in range(n):
		gold += land[i][0]
		if gold > land[i][1]:
			print "No"
			break
	else:
		print "Yes"

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == 0: break
    info = []
    for i in range(n):
        lu, w = map(int, raw_input().split())
        info.append((w, lu))
    info.sort()
    lu_sum = 0
    flag = True
    for w, lu in info:
        lu_sum += lu
        if lu_sum > w:
            flag = False
    print("Yes" if flag else "No")

Submission status: Accepted

Solution code:
def solve(info):
    have = 0
    for m, w in info:
        have += w
        if m < have:
            return "No"
    return "Yes"

while True:
    shima_count = input()
    if shima_count == 0: break
    info = []
    for i in range(shima_count):
        lu, w = map(int, raw_input().split())
        info.append((w, lu))
    info.sort()
    print solve(info)

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    a=[tuple(map(int,reversed(input().split()))) for _ in range(n)]
    a.sort()
    w=0
    for x,y in a:
        w+=y
        if x<w:print('No');break
    else:print('Yes')

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    bridges = []
    for _ in range(n):
        t, b = map(int, input().split())
        bridges.append((t, b))
    bridges.sort(key = lambda x: x[1])

    flag = True
    sumt = 0
    for t, b in bridges:
        sumt += t
        if sumt > b:
            flag = False
            break
    
    if flag:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0: break
    A=[[0,0] for i in range(n)] 
    for i in range(n):
        [a,b]=map(int,raw_input().split())
        A[i]=[a,b]
    A.sort(key= lambda x: x[1])
    s=0
    for i in range(n):
        if s+A[i][0]>A[i][1]:
            print 'No'
            break
        else:
            s+=A[i][0]
    else:
        print 'Yes'

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    cnt = total = 0
    for a, b in z:
        total += a
        if total > b:
            break
        cnt += 1
    print("Yes" if cnt == n else "No")

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    cnt = total = 0
    for a, b in z:
        total += a
        if total > b:
            cnt = 1
            break
    print("No" if cnt else "Yes")

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    z = sorted([tuple(map(int, input().split())) for _ in range(n)],  key=lambda x: x[1])
    total = 0
    for a, b in z:
        total += a
        if total > b:
            print("No")
            break
    else:
        print("Yes")

Submission status: Accepted

Solution code:
from sys import exit
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]

while True:
    flag = False
    n = int(input())
    if not(n):
        exit()
    islands = []
    for i in range(n):
        islands.append(f())
    islands.sort(key=lambda x:x[1])
    
    weight = 0
    for j in range(n):
        weight += islands[j][0]
        if weight > islands[j][1]:
            flag = True
            print("No")
            break
    if not(flag):
        print("Yes")

Submission status: Accepted

Solution code:
def sky(x):
    return x[1]


while True:
    n = int(input())
    if n == 0:
        break
    
    arr = [[] for i in range(n)]
    sumh = 0
    for i in range(n):
        arr[i] = list(map(int, input().split()))
    arr.sort(key=sky)
    res = True
    for e in arr:
        sumh += e[0]
        if sumh > e[1]:
            res = False
            break
    if res:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
def solve(l):
	have = 0
	for m, w in l:
		have += w
		if m < have:
			return "No"
	return "Yes"
while True:
	n = input()
	if n == 0: break
	l = [tuple(reversed(map(int, raw_input().split()))) for i in xrange(n)]
	l.sort()
	print solve(l)

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N == 0:
        break
    P = [list(map(int, input().split())) for i in range(N)]
    P.sort(key=lambda x: (-x[1], x[0]))
    su = sum(w for w, s in P)
    for w, s in P:
        if s < su:
            print("No")
            break
        su -= w
    else:
        print("Yes")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  lst = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[-1])
  acc = 0
  for w, b in lst:
    acc += w
    if acc > b:
      print("No")
      break
  else:
    print("Yes")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    n = int(raw_input())
    island = []
    if n == 0:
        break
    for i in range(n):
        g,b = map(int,input().split())
        island.append((g,b,b-g))
    sorted(island,key = lambda x:(x[2],[0],[1]))
    
    gem = 0
    for g,b,c in island:
        gem += g
        if b < gem:
            break
    else:
        print 'Yes'
        continue
    print 'No'

Submission status: Runtime Error

Solution code:
while True:
    count_shima=input()
    if count_shima==0: break

    A = [list(map(int,raw_input().split())) for i in xrange(count_shima)]

    A.sort()

    weight=0
    frg=0
    for takara,turi in A:
        weight +=takara
        if turi < weight:
            print "NO"
            frg=1
            break
    if frg==0:
        print "YES"

Submission status: Runtime Error

Solution code:
import sys
n = 1
a = []
while(True):
    n = (int)(input())
    if  n == 0:
        break
    for i in range(n):
       a.append(int(input().split())) 

a.sort(key=lambda x:x[1])
nimo = 0
for i in range(n):
    if(a[i][1] >= nimo+a[i][0]):
        nimo += a[i][0]
    else:
        print("No")
        sys.exit()
print("Yes")