Problem:


Score : 400 points

Problem Statement

A university student, Takahashi, has to take N examinations and pass all of them.
Currently, his readiness for the i-th examination is A_{i}, and according to his investigation, it is known that he needs readiness of at least B_{i} in order to pass the i-th examination.

Takahashi thinks that he may not be able to pass all the examinations, and he has decided to ask a magician, Aoki, to change the readiness for as few examinations as possible so that he can pass all of them, while not changing the total readiness.

For Takahashi, find the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the following conditions:

The sum of the sequence A_1, A_2, ..., A_{N} and the sum of the sequence C_1, C_2, ..., C_{N} are equal.

For every i, B_i \leq C_i holds.

If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^9

A_i and B_i are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_{N}
B_1 B_2 ... B_{N}

Output

Print the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the conditions.
If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.

Sample Input 1

3
2 3 5
3 4 1

Sample Output 1

3

(A_1, A_2, A_3) = (2, 3, 5) and (B_1, B_2, B_3) = (3, 4, 1). If nothing is done, he cannot pass the first and second exams.
The minimum possible number of indices i such that A_i and C_i are different, 3, is achieved when:

(C_1, C_2, C_3) = (3, 5, 2)

Sample Input 2

3
2 3 3
2 2 1

Sample Output 2

0

In this case, he has to do nothing in order to pass all the exams.

Sample Input 3

3
17 7 1
25 6 14

Sample Output 3

-1

In this case, no matter what is done, he cannot pass all the exams.

Sample Input 4

12
757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604
74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212

Sample Output 4

5



Sample input:
3
2 3 5
3 4 1


Sample output:
3

Submission status: Accepted

Solution code:
#from statistics import median
import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
#from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
B = readInts()
num = 0
minus = 0
box = []
for i in range(n):
    diff = A[i] - B[i]
    if diff < 0:
        minus -= diff
        num += 1
    else:# プラスの分を足していく
        box.append(diff)
box = sorted(box,reverse = True)
if num == 0:
    print(0)
else:
    # 大きい方から＋の和を取っていって、それが－の合計以上になったらもうやらなくていいよ
    plus = 0
    for a in box:
        plus += a
        num += 1
        if plus >= minus:
            break
    if plus >= minus:
        print(num)
    else:
        print(-1)

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))
remain = 0
ans = 0
li = []
for a, b in zip(An, Bn):
    if a >= b:
        li.append(a-b)
    else:
        ans += 1
        remain += (b-a)
if sum(li) < remain:
    ans = -1
elif ans == 0:
    pass
else:
    temp = 0
    for num in sorted(li, reverse=True):
        if temp >= remain:
            break
        temp += num
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
A = LIST()
B = LIST()

if sum(A) < sum(B):
	print(-1)
	exit()

l = [A[i]-B[i] for i in range(N)]
l.sort()

idx = bisect_left(l, 0)
p = sum(l[:idx])

tmp = 0
ans = idx 
i = 0

while tmp + p < 0:
	i += 1
	tmp += l[-i]
	

print(ans + i)

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
B = list(map(int, sys.stdin.readline().rsplit()))
C = [0] * N

s = 0
minus = 0
res = 0
for i in range(N):
    c = A[i] - B[i]
    C[i] = c
    s += c
    if c < 0:
        minus += c
        res += 1

if s < 0:
    print(-1)
else:
    C.sort(reverse=True)
    s = 0
    for i, c in enumerate(C):
        if s + minus >= 0:
            print(res + i)
            exit()
        s += c

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(e) for e in input().split()]
B_list = [int(e) for e in input().split()]

#B-Aで過剰/不足を取得
#過剰を並び替え、大きいものから不足に割り当てていく

shortage_list = list()
surplus_list = list()

for i in range(N):
    C = B_list[i]-A_list[i]
    if C > 0:
        shortage_list.append(C)
    elif C < 0:
        surplus_list.append(-C)
        
if sum(surplus_list) < sum(shortage_list):
    print(-1)
elif len(shortage_list) == 0:
    print(0)
else:
    surplus_list.sort(reverse=True)
    sum_shortage = sum(shortage_list)
    for i in range(len(surplus_list)):
        sum_shortage -= surplus_list[i]
        if sum_shortage <= 0:
            print(i + 1 + len(shortage_list))
            break

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
b=lmp()
sa=sum(a)
sb=sum(b)
l=[]
if sb>sa:
    print(-1)
    exit()
for i in range(n):
    l.append(-b[i]+a[i])
l=sorted(l,reverse=True)

r=[0]
s=0
ans=0
m=0
for i in range(n):
    if l[i]>0:
        s+=l[i]
        r.append(s)
    elif l[i]<0:
        ans+=1
        m+=l[i]
for i in range(len(r)):
    if m+r[i]>=0:
        print(ans+i)
        exit()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
Bs = list(mapint())

if sum(As)<sum(Bs):
    print(-1)
else:
    diff = [a-b for a, b in zip(As, Bs)]
    diff.sort()
    cnt = 0
    need = 0
    for d in diff:
        if d>=0:
            break
        need += d
        cnt += 1
    for d in diff[::-1]:
        if need>=0:
            break
        need += d
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    sA = sum(A)
    sB = sum(B)
    if sA < sB:
        return print(-1)
    C = [a-b for a, b in zip(A, B)]
    C.sort()
    ans = 0
    less = 0
    for c in C:
        if c < 0:
            ans += 1
            less += c
        else:
            break
    for c in C[::-1]:
        if 0 <= less:
            break
        less += c
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
if sum(B) > sum(A):
  print("-1")
  exit()
D = []
for i in range(N):
  D.append(A[i]-B[i])
D.sort()
#print(D)
num = 0
s = 0; t = -1
yoyu = 0
while D[s] < 0:
  if yoyu+D[s] <0:
    num += 1 #ここで一番余裕があるのを取り出す。
    yoyu += D[t]
    t -= 1
  num += 1 #ここで足りない分が足された試験
  yoyu += D[s]
  s += 1
print(num)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

pu = []
ma = []
for x, y in zip(a, b):
    if x - y < 0:
        ma.append(x - y)
    else:
        pu.append(x - y)
if sum(pu) + sum(ma) < 0:
    print(-1)
else:
    cnt = len(ma)
    ma_sum = sum(ma)
    pu.sort(reverse = True)
    while ma_sum < 0:
        cnt += 1
        ma_sum += pu.pop(0)
    print(cnt)

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,A:list,B:list) -> int:
   negative = []
   positive = []
   counter = 0
   total = 0
   for a,b in zip(A,B):
      if(a - b < 0):
         negative.append(a - b)
      else:
         positive.append(a - b)
   negative.sort()
   positive.sort(reverse=True)
   for d in negative + positive:
      if(d >= 0 and total >= 0):
         break
      else:
         total += d
         counter += 1
   
   return counter if(total >= 0) else -1

def modelAnswer():
   return
def main():
   N = int(input())
   A = list(map(int,input().split()))
   B = list(map(int,input().split()))
   print(myAnswer(N,A,B))

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a)<sum(b):
    print(-1)
    exit()

p=0

ori_d=[]
for i in range (N):
    _d=a[i]-b[i]
    ori_d.append([i,_d])

d=sorted(ori_d,key=lambda x: x[1])
d2=[0]*N
for j in range (N):
    if d[j][1]>=0:
        break
    else:
        p+=abs(d[j][1])
        d2[j]+=1

for k in range (N-1,0,-1):
    if p==0:
        break
    elif d[k][1]<p:
        p-=d[k][1]
        d[k][1]=0
        d2[k]+=1
    else:
        d[k][1]-=p
        p=0
        d2[k]+=1

print(sum(d2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
if sum(a) < sum(b):
    ans = -1
else:
    c = [b[i] - a[i] for i in range(n)]
    c.sort()
    c_minus = [cc for cc in c if cc > 0]
    if len(c_minus) == 0:
        ans = 0
    else:
        aaa = 0
        point = sum(c_minus)
        for i in range(n):
            point += c[i]
            if point <= 0:
                break
        ans = len(c_minus) + i + 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
if sum(a_list)<sum(b_list):
    print(-1)
else:
    diff_list = [a_list[i]-b_list[i] for i in range(n)]
    posi_heap=[]
    heapq.heapify(posi_heap)
    cnt,diff_sum = 0,0
    for diff in diff_list:
        if diff<0:
            cnt+=1
            diff_sum+=diff
        elif diff>0:
            heapq.heappush(posi_heap,-1*diff)
    diff_sum*=(-1)
    i=0
    while diff_sum>0:
        diff_sum+=heapq.heappop(posi_heap)
        i+=1
    print(i+cnt)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
if sum(a_list)<sum(b_list):
    print(-1)
else:
    diff_list = [a_list[i]-b_list[i] for i in range(n)]
    posi_list=[]
    cnt,diff_sum = 0,0
    for diff in diff_list:
        if diff<0:
            cnt+=1
            diff_sum+=diff
        elif diff>0:
            posi_list.append(diff)
    diff_sum*=(-1)
    posi_list.sort(reverse=True)
    i,S=0,0
    while S<diff_sum:
        S+=posi_list[i]
        i+=1
    print(i+cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(B) > sum(A):
    print(-1)

ab = [0]*N
for i in range(N):
    ab[i] = A[i]-B[i]

ab.sort()

ans = 0
minus_sum = 0
for i in range(N):
    if ab[i] >= 0:
        break
    minus_sum += ab[i]
    ans += 1

for i in reversed(range(N)):
    if minus_sum >= 0:
        print(ans)
        exit(0)

    minus_sum += ab[i]
    ans += 1

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

under = 0
over = []
cnt = 0

for i in range(N):
    if B[i] > A[i]:
        under += B[i] - A[i]
        cnt += 1
    elif B[i] < A[i]:
        over.append(A[i] - B[i])

over.sort(reverse=True)


# print("u", under)
# print("o", over)

for s in over:
    if under <= 0:
        break
    under -= s
    cnt += 1

if under <= 0:
    print(cnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()
B = IL()

if sum(A)<sum(B):
  print(-1)
else:
  C = [A[i]-B[i] for i in range(N)]
  C.sort()
  D = 0
  count = 0
  for c in C:
    if c < 0:
      D += c
      count += 1
    if c >= 0:
      break
  for c in C[::-1]:
    if D<0:
      D += c
      count += 1
    if D >= 0:
      break
  print(count)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

c=[]
need=sum(a)-sum(b)
ans=0
for i in range(n):
    c.append(a[i]-b[i])
    
c=sorted(c)
arr=np.array(c)
arr2=arr[arr>=0]
d=arr2.tolist()
#print(need,d)
for i in range(len(d)):
    need-=d[i]
    if need>=0:
        ans+=1
#print(ans)
if sum(a)<sum(b):
    print(-1)
else:
    print(n-ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if sum(A) < sum(B):
    print(-1)
    exit()
neg_diffs = []
pos_diffs = []
for a, b in zip(A, B):
    if a < b:
        neg_diffs.append(b - a)
    else:
        pos_diffs.append(a - b)
if len(pos_diffs) == N:
    print(0)
    exit()
cnt = 0
neg_sum = sum(sorted(neg_diffs))
for pos_diff in sorted(pos_diffs, reverse=True):
    if neg_sum <= 0:
        break
    neg_sum -= pos_diff
    cnt += 1
print(cnt + len(neg_diffs))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))

    surplus_scores = []
    sum_lack_score = 0
    ans = 0
    for a, b in zip(A, B):
        if a > b:
            surplus_scores.append(a - b)
        elif a < b:
            sum_lack_score += b - a
            ans += 1

    if sum_lack_score > 0:
        surplus_scores.sort(reverse=True)
        pass_exam = False
        for i, score in enumerate(surplus_scores):
            sum_lack_score -= score
            if sum_lack_score <= 0:
                ans += (i + 1)
                pass_exam = True
                break
        if not pass_exam:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    surplus_scores = []
    sum_lack_score = 0
    ans = 0
    for a, b in zip(A, B):
        if a > b:
            surplus_scores.append(a - b)
        elif a < b:
            sum_lack_score += b - a
            ans += 1

    if sum_lack_score > 0:
        surplus_scores.sort(reverse=True)
        pass_exam = False
        for i, score in enumerate(surplus_scores):
            sum_lack_score -= score
            if sum_lack_score <= 0:
                ans += (i + 1)
                pass_exam = True
                break
        if not pass_exam:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    surplus_scores = []
    sum_lack_score = 0
    ans = 0
    for a, b in zip(A, B):
        if a > b:
            surplus_scores.append(a - b)
        elif a < b:
            sum_lack_score += b - a
            ans += 1

    if sum_lack_score > 0:
        surplus_scores.sort(reverse=True)
        pass_exam = False
        for score in surplus_scores:
            sum_lack_score -= score
            ans += 1
            if sum_lack_score <= 0:
                pass_exam = True
                break
        if not pass_exam:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    surplus_scores = []
    sum_lack_score = 0
    ans = 0
    for a, b in zip(A, B):
        if a > b:
            surplus_scores.append(a - b)
        elif a < b:
            sum_lack_score += b - a
            ans += 1

    surplus_scores.sort(reverse=True)
    if sum_lack_score > 0:
        pass_exam = False
        for score in surplus_scores:
            sum_lack_score -= score
            ans += 1
            if sum_lack_score <= 0:
                pass_exam = True
                break
        if not pass_exam:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
D = []
ans = 0
for i in range(N):
    D.append(A[i]-B[i])
DMINUS = list(filter(lambda x: x < 0,D))
ans += len(DMINUS)
MINUSSUM = sum(DMINUS)
DPULUS = sorted(filter(lambda x: x > 0,D),key=lambda x: -x)
for d in DPULUS:
    if MINUSSUM >= 0:
        break
    MINUSSUM += d
    ans += 1
if MINUSSUM < 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [0]
D = [0]

for i in range(N):
    s = B[i] - A[i]
    if(s > 0):
        C.append(s)
    elif(s < 0):
        D.append(s)

D = sorted(D)

csum = sum(C)
dsum = sum(D)

if(csum + dsum > 0):
    print(-1)
elif(csum == 0):
    print(0)
else:
    ans = len(C) -1
    for i in D:
        csum += i
        ans += 1
        if(csum <= 0):
            break
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[]
for i in range(n):
    c.append((a[i],b[i]))
c=sorted(c,key=lambda x:x[0]-x[1])
x=0
ans = 0
j = 0
for i in range(n):
    if c[i][0]-c[i][1] <0:
        ans += 1
        x += abs(c[i][0]-c[i][1])
    else:
        j=i
        break
for i in range(n-1,j-1,-1):
    if j == 0:
        break
    x-=c[i][0]-c[i][1]
    ans+= 1
    if x<=0:
        break
    
if x<=0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [A[i]-B[i] for i in range(N)]
if sum(A) < sum(B):
    print(-1)
    exit()
C.sort()
d = 0
ans = 0
for c in C:
    if c >= 0:
        break
    d += c
    ans += 1
C.reverse()
for i in range(N):
    if d >= 0:
        break
    d += C[i]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    ans = 0

    remain = []
    lack = 0
    for i in range(N):
        diff = A[i] - B[i]
        if diff > 0:
            remain.append(diff)
        if diff < 0:
            lack += abs(diff)
            ans += 1

    if lack == 0:
        print("0")
        return
    
    remain.sort(reverse=True)
    sm = 0
    for r in remain:
        sm += r
        ans += 1
        if sm >= lack:
            print(ans)
            break
    else:
        print("-1")
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
D=[i-j for i,j in zip(a,b)]
c=[i for i in D if i>0]
c.sort()
d=[i for i in D if i<0]

e=sum(d)
if sum(a)<sum(b):
    print(-1)
elif len(d)==0:
    print(0)
else:
    ans=0
    for i in c[::-1]:
        ans+=1
        e+=i
        if e>=0:
            print(ans+len(d))
            exit()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    res = 0
    if sum(A) < sum(B):
        print(-1)
        exit()

    # まず不足している準備度を求める
    # また、余ってたら余ってる量をCにブチこんでいく
    C = list()
    missing = 0
    ans = 0
    for i in range(N):
        if A[i] < B[i]:
            missing += (B[i] - A[i])
            ans += 1
        else:
            C.append(A[i]-B[i])

    if missing == 0:
        print(0)
        exit()

    C.sort(reverse=True)

    for c in C:
        if missing <= c:
            ans += 1
            break
        else:
            missing -= c
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(A) < sum(B):
    print(-1)
    exit()

ans = 0
minus = 0
plus_list = []
for a, b in zip(A, B):
    if a < b:
        ans += 1
        minus += b - a
    plus_list.append(a - b)

if minus == 0:
    print(0)
    exit()

plus_list_ = sorted(plus_list, reverse=True)

for p in plus_list_:
    minus -= p
    ans += 1
    if minus < 0:
        break

print(ans)
#print(minus)
#print(plus_list)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
if sum(b) > sum(a):
  print(-1)
  exit()
d = []
minus = 0
minussum = 0
for i in range(n):
  k = a[i] - b[i]
  if k < 0:
    minus += 1
    minussum += k
  else:
    d.append(k)
d.sort(reverse=True)
for f in d:
  if minussum >= 0:
    print(minus)
    exit()
  minus += 1
  minussum += f
print(minus)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = []
ans = 0
m = 0
if sum(a) < sum(b):
    print(-1)
    exit()
for i in range(n):
    if a[i] < b[i]:
        ans += 1
        m += b[i] - a[i]
    else:
        l.append(a[i] - b[i])
l = list(reversed(sorted(l)))
for i in l:
    if m > 0:
        m -= i
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

if sum(a_list) < sum(b_list):
    print(-1)
    exit()

a_sub_b = [a_list[i] - b_list[i] for i in range(n)]
insufficients = [x for x in a_sub_b if x < 0]

cnt = len(insufficients)
sum_insuf = sum(insufficients)
for x in sorted(a_sub_b, reverse=True):
    if sum_insuf >= 0:
        break
    sum_insuf += x
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a)<sum(b):
    print(-1)
else:
    s=0
    k=[]
    m=0
    for i in range(n):
        d=a[i]-b[i]
        if d>=0:
            k.append(d)
        else:
            m+=d
            s+=1
    k.sort(reverse=True)
    j=0
    while m<0:
        m+=k[j]
        s+=1
        j+=1
    print(s)

Submission status: Accepted

Solution code:
import sys
N=int(input())
C=list()
A=list(map(int,input().split()))
B=list(map(int,input().split()))
R=0
k=0
if sum(B)>sum(A):
  print(-1)
  sys.exit()
for i in range(N):
  C.append(A[i]-B[i])
C=sorted(C)
for i in range(N):
  if C[i]<0:
    R=R+C[i]
    k=k+1
C=sorted(C,reverse=True)
for i in range(N):
  if R==0:
    print(0)
    sys.exit()
  R=R+C[i]
  if R>=0:
    print(k+i+1)
    sys.exit()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(A) < sum(B):
  print(-1)
  quit()

ans = 0
diff = 0
larger = []
for a, b in zip(A, B):
  if a < b:
    ans += 1
    diff += b - a
  else:
    larger.append(a - b)

larger.sort(reverse=True)
for l in larger:
  if diff > 0:
    diff -= l
    ans += 1
  else:
    break

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    diff_AB = sum(A) - sum(B)

    if diff_AB < 0:
        print(-1)
        exit()

    Diff = []
    for i in range(n):
        Diff.append(A[i] - B[i])

    Diff.sort()

    res = 0
    for j in range(n):
        if Diff[j] < 0:
            res += 1
        else:
            if Diff[j] <= diff_AB:
                diff_AB -= Diff[j]
            else:
                diff_AB = 0
                res += 1

    if diff_AB > 0:
        res += 1

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
A= list(map(int,input().split()))
sum_A=sum(A)
B= list(map(int,input().split()))
ans=0
if sum_A < sum(B):
   print(-1)
   exit()
l=[]
S=0
for i in range(N):
   if A[i]<B[i]:
      ans+=1
      S+=B[i]-A[i]
   elif A[i]>=B[i]:
      l.append(A[i]-B[i])
l.sort(reverse=True)
cnt=0
for i in l:
   if S>0:
      S-=i
      cnt+=1
print(ans+cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(A) < sum(B):
    print(-1)
else:
    minus_count = []
    plus_count = []
    for i in range(N):
        dist = A[i] - B[i]
        if dist > 0:
            plus_count.append(dist)
        elif dist < 0:
            minus_count.append(dist)
    plus_count.sort()
    minus_sum = sum(minus_count)
    count = len(minus_count)
    while minus_sum < 0:
        minus_sum += plus_count.pop()
        count += 1
    print(count)

Submission status: Accepted

Solution code:
n,*d=map(int,open(0).read().split());f=[d[i]-d[n+i]for i in range(n)];m=[v for v in f if v<0];p=sorted(v for v in f if v>0);c=len(m);s=sum(m)
while s<0and p:s+=p.pop();c+=1
print([c,-1][s<0])

Submission status: Accepted

Solution code:
n,*d=map(int,open(0).read().split())
f=[d[i]-d[n+i]for i in range(n)]
m=[v for v in f if v<0];p=sorted(v for v in f if v>0)
c=len(m);s=sum(m)
while s<0and p:s+=p.pop();c+=1
print([c,-1][s<0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x, y = [], []
for i in range(n):
    if a[i] > b[i]:
        x.append(a[i] - b[i])
    else:
        y.append(b[i] - a[i])
ans = -1
if sum(x) >= sum(y):
    if sum(y) == 0:
        ans = 0
    else:
       dif = sum(x) - sum(y)
       x = sorted(x)
       index = 0
       total = 0
       while total + x[index] <= dif:
           total += x[index]
           index += 1
       ans = n - index
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=[a[i]-b[i] for i in range(n)]
if sum(x)<0:
  print(-1)
  exit()
x.sort()
if x[0]>=0:
  print(0)
  exit()
ans=0
m=0
while x[ans]<0:
  ans+=1
m=sum(x[:ans])
x=x[ans:][::-1]
i=0
while True:
  m+=x[i]
  i+=1
  if m>0:
    break
ans+=i
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b):
    ans = -1
else:
    d = [a[i]-b[i] for i in range(n)]
    d.sort()
    
    i = 0
    s = 0
    while d[i] < 0:
        s -= d[i]
        i += 1
    
    j = 0
    tmp = 0
    while s > tmp:
        tmp += d[j-1]
        j -= 1
    ans = i-j
print(ans)