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:
N= int(input())
A  = list(map(int,input().split()))
B  = list(map(int,input().split()))
short = []
margine = []
for a,b in zip(A,B):
    if a > b :
        margine.append(a-b)
    elif b > a:
        short.append(b-a)
        
ss = sum(short)
sc = len(short)
margine.sort()
if ss>sum(margine):
    print(-1)
    exit()
while ss>0:
    ss -= margine.pop()
    sc += 1
print(sc)

Submission status: Accepted

Solution code:
N= int(input())
A  = list(map(int,input().split()))
B  = list(map(int,input().split()))
short = []
margine = []
for a,b in zip(A,B):
    if a > b :
        margine.append(a-b)
    elif b > a:
        short.append(b-a)
        
ss = sum(short)
sc = len(short)
margine.sort()
if sum(short)>sum(margine):
    print(-1)
    exit()
while ss>0:
    ss -= margine.pop()
    sc += 1
print(sc)

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

C = [A[k]-B[k] for k in range(N)]
C.sort()
t = 0
ans = 0
for k in range(N):
    if C[k] >= 0:
        break
    else:
        t -= C[k]
        ans += 1

for k in range(N-1,-1,-1):
    if t <= 0:
        break
    else:
        t -= C[k]
        ans += 1

print(ans)

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,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
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:
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))
  C = []
  for a,b in zip(A,B):
    C.append(a-b)
  if sum(C)<0:
    return -1
  minus = sum([abs(x) for x in C if x<0])
  ans = len([abs(x) for x in C if x<0])
  C.sort(reverse=True)
  for i in range(N):
    if minus==0:
      break
    if C[i]>0:
      ans += 1
      if minus>C[i]:
        minus -= C[i]
      else:
        minus = 0
  return ans
print(solve())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = sorted([A[i]-B[i] for i in range(N)],reverse=True)
cp = 0
cm = 0
cnt = 0
for i in range(N):
    if C[i]>0:
        cp += C[i]
    elif C[i]<0:
        cnt += 1
        cm += -C[i]
if cm>cp:
    print(-1)
elif cnt==0:
    print(0)
else:
    cur = 0
    tot = C[cur]
    for i in range(N):
        if C[i]<0:
            while tot-abs(C[i])<0:
                tot += C[cur+1]
                cur += 1
            tot += C[i]
    print(cur+1+cnt)

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:
from collections import deque
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# Aの総和 = Cの総和
p = []
cnt_p = 0
cnt_m = 0
x = 0
for a,b in zip(A,B):
    if a > b:
        cnt_p += 1
        p.append(a-b)
    elif a < b:
        cnt_m += 1
        x += b-a

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

p = deque(sorted(p)[::-1])
while p and x > 0:
    P = p.popleft()
    if P <= x: x -= P
    else: x = 0
if x == 0:
    print(cnt_m+cnt_p-len(p))
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
D = [a-b for a,b in zip(A,B)]
D.sort()

lack = sum(d for d in D if d<0)

ans = 0
for d in D[::-1]:
    if lack < 0 and d > 0:
        ans += 1
        lack += d
    if d < 0:
        ans += 1
print(-1 if lack < 0 else ans)

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))
  C = [a-b for a,b in zip(A,B)]
  if sum(C)<0:
    return -1
  c = sum([-a for a in C if a<0])
  C.sort(reverse=True)
  ans = 0
  for i in range(N):
    if C[i]<0:
      ans += 1
      continue
    if C[i]==0 or c==0:
      continue
    c = max(c-C[i],0)
    ans += 1
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = [a[i]-b[i] for i in range(n)]
l.sort()
if sum(l)<0:
    ans = -1
else:
    s = sum(l[i] for i in range(n) if l[i]<0)
    if s>=0:
        ans = 0
    else:
        for j in range(n-1, -1, -1):
            s += l[j]
            if s>=0:
                break
        ans = sum(l[i]<0 for i in range(n)) + (n-j)
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):
    print(-1)
    exit()

l = []
cnt,low = 0,0
for i in range(N):
    if A[i] > B[i]:
        l.append(A[i]-B[i])
    if A[i] < B[i]:
        cnt += 1
        low += B[i] - A[i]

cnt2 = 0
l.sort(reverse=True)
for i in range(len(l)):
    if low <= 0:
        break
    low -= l[i]
    cnt2 += 1
print(cnt + cnt2)

Submission status: Accepted

Solution code:
n=int(input())
c=[]
d=[]
for a,b in zip(map(int,input().split()),map(int,input().split())):
  e=a-b
  if e<0:
    c.append(e)
  else:
    d.append(e)
if sum(c)+sum(d)<0:
  print(-1)
  exit()

cs=-sum(c)
d.sort(reverse=True)
sm=0
i=0
while sm<cs:
  sm+=d[i]
  i+=1
print(i+len(c))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
diff_po = [0]*n
diff_ne = 0
ans = 0
for i in range(n):
    num = a[i]-b[i]
    if num >= 0:
        diff_po[i] = num
    else:
        diff_ne += num
        ans += 1
diff_ne = -diff_ne
if sum(diff_po) < diff_ne:
    print(-1)
    exit()

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

diff_po.sort(reverse=1)
for i in diff_po:
    ans += 1
    diff_ne -= i
    if diff_ne <= 0:
        print(ans)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import *

n = int(input())
(*A, ) = map(int, input().split())
(*B, ) = map(int, input().split())
S = [A[i] - B[i] for i in range(n)]
if sum(S) < 0:
    print(-1)
    exit()
S.sort()
neg = bisect_left(S, 0)
pos = bisect_right(S, 0)
ne = sum(S[:pos])
rui = [0]
for i in reversed(S[pos:]):
    rui.append(rui[-1] + i)
print(neg + bisect_left(rui, -ne))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import *

n = int(input())
(*A, ) = map(int, input().split())
(*B, ) = map(int, input().split())
S = [A[i] - B[i] for i in range(n)]
if sum(S) < 0:
    print(-1)
    exit()
S.sort()
neg = bisect_left(S, 0)
pos = bisect_right(S, 0)
ne = sum(S[:pos])
rui = [S[-1]]
for i in reversed(S[pos:n - 1]):
    rui.append(rui[-1] + i)
print(neg + bisect_left(rui, -ne) + (neg != 0))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
sumA = sum(A)
sumB = sum(B)
if sumA<sumB:exit(print(-1))
surplus = [0]*n
for i in range(n):
    surplus[i] = A[i]-B[i]
surplus.sort()

index_zero = bisect.bisect_left(surplus,0)
reqt = sum(surplus[:index_zero])
ans = index_zero
index_ = n-1
#print(surplus, index_zero, reqt)
while reqt < 0:
    reqt += surplus[index_]
    index_ -= 1
    ans += 1
print(ans)

Submission status: Accepted

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

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

Plus.sort()
i=0
M=len(Plus)
Plus=Plus[::-1]
while Minus>0 and i<M:
    ans+=1
    Minus-=Plus[i]
    i+=1

if Minus>0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# keyence2019_c.py
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
if sum(A)<sum(B):
    print(-1)
    exit()

C = []
diff = 0
cnt = 0
for i in range(N):
    d = A[i] - B[i]
    if d < 0:
        cnt += 1
        diff += d
    else:
        C.append(d)
C.sort(reverse=True)
for i in C:
    if diff >= 0:
        break 
    diff += i
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import heapq
n= int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
suma,sumb = sum(al),sum(bl)
if suma<sumb:print(-1)
else:
    hpl=[]
    heapq.heapify(hpl)
    hml=[]
    heapq.heapify(hml)
    for i in range(n):
        if (dif:=al[i]-bl[i])>=0:heapq.heappush(hpl,-dif)
        else:heapq.heappush(hml,-dif)
    if len(hml)==0:
        print(0)
    else:
        count=0
        usem=False
        usep=False
        while len(hpl)!=0 and len(hml)!=0:
            pp = -hpl[0]
            mm = hml[0]
            if pp>mm:
                hpl[0]+=hml[0]
                heapq.heappop(hml)
                usem=False
                count +=1                    
                usep=True
            elif pp<mm:
                hml[0]+=hpl[0]
                heapq.heappop(hpl)
                usep=False
                count +=1
                usem=True
            else:
                heapq.heappop(hpl)
                usep=False
                count+=1
                heapq.heappop(hml)
                usem=False
                count+=1                 
        if usem:count+=1
        if usep:count+=1
        print(count)

Submission status: Accepted

Solution code:
n = int(input())
now_ls = list(map(int, input().split()))
target_ls = list(map(int, input().split()))
if sum(now_ls) < sum(target_ls):
    print(-1)
else:
    ans = 0
    lack = 0
    surplus_ls = []
    for i in range(n):
        if now_ls[i] < target_ls[i]:
            ans += 1
            lack += target_ls[i] - now_ls[i]
        else:
            surplus_ls.append(now_ls[i] - target_ls[i])
    surplus_ls.sort()
    while lack > 0:
        ans += 1
        nex = surplus_ls.pop()
        lack -= nex
    print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if sum(A) < sum(B):
    print(-1)
    sys.exit()
V = []
Vp = V.append
_V = []
_Vp = _V.append
for i in range(N):
    d = A[i] - B[i]
    if d > 0:
        Vp(d)
    elif d < 0:
        _Vp(-d)
if len(_V) == 0:
    print(0)
    sys.exit()
V.sort()
_V.sort()
i = len(V) - 1
_i = len(_V) - 1
t = 0
res = 0
while _i >= 0:
    if t < 0:
        t += V[i]
        i -= 1
        res += 1
    else:
        t -= _V[_i]
        _i -= 1
        res += 1
print(res + int(t < 0))

Submission status: Accepted

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

# In[43]:


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


# In[45]:


# if sum(A) < sum(B):
#     ans = -1
# else:
#     diff_plus = sorted([B[i]-A[i] for i in range(N) if B[i]-A[i]>0])
#     diff_minus = sorted([A[i]-B[i] for i in range(N) if A[i]-B[i]>0],reverse=True)
#     if len(diff_plus) > 0:
#         j = 0
#         cnt = len(diff_plus)
#         for i,x in enumerate(diff_plus):
#             while sum(diff_minus[:j+1]) < x:
#                 j += 1
#             diff_minus[j] = sum(diff_minus[:j+1])-x
#             for k in range(j):
#                 diff_minus[k] = 0
#         ans = j+1+cnt
#     else:
#         ans = 0
# print(ans)


# In[47]:


husoku = [a-b for a, b in zip(A, B) if a-b < 0]
amari = [a-b for a, b in zip(A, B) if a-b > 0]
amari.sort(reverse=True)
 
H = abs(sum(husoku))
if len(husoku) == 0:
    ans = 0
elif H > sum(amari):
    ans = -1
else:
    for i, a in enumerate(amari, start=1):
        H -= a
        if H <= 0:
            ans = len(husoku) + i
            break
print(ans)


# In[ ]:

Submission status: Accepted

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

m=0
c=0
for i in range(N):
    if B[i]>A[i]:
        m+=B[i]-A[i]
        c+=1

li=[]
for i in range(N):
    if B[i]<A[i]:
        li.append(A[i]-B[i])
li.sort(reverse=True)
for k in li:
    if m==0:
        break
    m-=min(m,k)
    c+=1
print(c if m==0 else -1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
na=sorted(a)
nb=sorted(b)
c=[0]*n
for i in range(n):
  c[i]=a[i]-b[i]
if sum(c)<0:
  print(-1)
else:
  c.sort()
  ans=0
  s=0
  for i in range(n):
    if c[i]<0:
      s=s+abs(c[i])
      ans=ans+1
  for i in range(n):
    if s<=0:
      break
    else:
      s=s-c[n-i-1]
      ans=ans+1
  print(ans)

Submission status: Accepted

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

#%%
husoku = [a-b for a, b in zip(A, B) if a-b < 0]
amari = [a-b for a, b in zip(A, B) if a-b > 0]
amari.sort(reverse=True)

H = abs(sum(husoku))
if len(husoku) == 0:
    ans = 0
elif H > sum(amari):
    ans = -1
else:
    for i, a in enumerate(amari, start=1):
        H -= a
        if H <= 0:
            ans = len(husoku) + i
            break

print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
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)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
b = lr()
if sum(b) > sum(a):
    print(-1)
else:
    p = []
    m = []
    for i in range(n):
        if a[i] > b[i]:
            p.append(a[i]-b[i])
        elif a[i] < b[i]:
            m.append(b[i]-a[i])
    p.sort(reverse=True)
    t = sum(m)
    ans = 0
    total = 0
    for num in p:
        if total < t:
            total+=num
            ans+=1
        else:
            break
    print(ans+len(m))

Submission status: Accepted

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

excess = []
shortage = []

ans = 0

for i in range(n):
    if a[i] >= b[i]:
        excess.append(a[i] - b[i])
    else:
        shortage.append(b[i] - a[i])

ans = len(shortage)

if sum(excess) < sum(shortage):
    print(-1)
elif len(shortage) == 0:
    print(0)
else:
    excess.sort(reverse=True)
    excess_num = 0
    shortage_num = sum(shortage)
    for i in range(n):
        excess_num += excess[i]
        ans += 1
        if excess_num >= shortage_num:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N = int(input())
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    Ds = [a - b for a, b in zip(As, Bs)]

    cnt_minus = 0
    total_minus = 0
    minus_list = []

    cnt_plus_to_drow = 0
    plus_list = []

    for item in Ds:
        if item < 0:
            cnt_minus += 1
            total_minus += item
        else:
            plus_list.append(item)

    plus_list.sort()

    if sum(plus_list) >= abs(total_minus):
        for item in plus_list[::-1]:
            if total_minus >= 0:
                break

            total_minus += item
            cnt_plus_to_drow += 1

        print(cnt_minus + cnt_plus_to_drow)
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
"""
準備度の余剰分を不足分に充てる。
なるべく余剰分が大きいものから割り振っていく。
"""
N = int(input())
A_LI = list(map(int, input().split()))
B_LI = list(map(int, input().split()))
shortage_list = []
surplus_list = []
for i in range(N):
    if A_LI[i] == B_LI[i]:
        # 余剰(不足)分0のやつがリストに入ることを避けたいのでこうしとく↓
        continue
    elif A_LI[i] < B_LI[i]:
        shortage_list.append(B_LI[i] - A_LI[i])
    else:
        surplus_list.append(A_LI[i] - B_LI[i])
shortage_list.sort(reverse=True)
surplus_list.sort(reverse=True)
if sum(shortage_list) > sum(surplus_list):
    print(-1)
else:
    if len(shortage_list) == 0:
        print(0)
        exit()
    shortage_idx = 0
    surplus_idx = 0
    shortage = shortage_list[0]
    surplus = surplus_list[0]
    surplus_change_cnt = 1
    while shortage_idx < len(shortage_list):
        tmp = min(shortage, surplus)
        shortage -= tmp
        surplus -= tmp
        # 0以下になったらおかわりする
        if shortage <= 0:
            shortage_idx += 1
            if shortage_idx == len(shortage_list):
                break
            shortage += shortage_list[shortage_idx]
        elif surplus <= 0:
            surplus_idx += 1
            if shortage_idx == len(shortage_list):
                break
            surplus += surplus_list[surplus_idx]
            surplus_change_cnt += 1
    print(len(shortage_list) + surplus_change_cnt)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	bl = lin()
	diff = [a-b for a,b in zip(al, bl)]
	diff.sort()
	if sum(diff) < 0:
		return -1
	tarinai = [v for v in diff if v < 0]
	ret = len(tarinai)
	#pa(ret)
	tv = sum(tarinai)
	if tv >= 0:
		return 0
	#pa(diff)
	for v in diff[::-1]:
		tv += v
		ret += 1
		if tv >= 0:
			break
	return ret

	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
N=int(input())
a=input().split()
A=[int(c) for c in a]
b=input().split()
B=[int(d) for d in b]

sum_A=sum(A)
sum_B=sum(B)

sa=[]
for n in range(N):
    number=A[n]-B[n]
    sa.append(number)
new_sa=sorted(sa)
plus=[]
minus=[]
for n in new_sa:
    if n>=0:
        plus.append(n)
    else:
        minus.append(n)

saishou=abs(sum(minus))
new_plus=sorted(plus,reverse=True)
answer=len(minus)
n_plus=[]
n_plus.append(new_plus[0])
del new_plus[0]
for plu in new_plus:
    n_plus.append(n_plus[-1]+plu)

if sum_A<sum_B:
    print(-1)
else:
    if answer==0:
        print(answer)
    else:
        number=1
        for suuji in n_plus:
            if suuji>=saishou:
                print(answer+number)
                break
            else:
                number+=1

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:
    p = []
    m = []
    for i in range(N):
        if(B[i]-A[i] <= 0):
            p.append(A[i]-B[i])
        else:
            m.append(B[i]-A[i])
    p.sort(reverse=True)
    ans = len(m)
    idx = 0
    res = sum(m)
    while res > 0:
        if(p[idx] == 0):
            idx += 1
            continue
        res = res - p[idx]
        ans += 1
        idx += 1

    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):
    print(-1)
    exit(0)
ans = 0
tarinai = 0
yobun = []
for i in range(n):
    if a[i] < b[i]:
        ans += 1    
        tarinai += b[i] - a[i]
    elif a[i] > b[i]:
        yobun.append(a[i] - b[i])
if ans == 0:
    print(0)
    exit(0)
yobun.sort(reverse=True) 
m = len(yobun)
total = 0
for i in range(m):  
    total += yobun[i]
    if total >= tarinai:
        ans += i + 1
        break
print(ans)

Submission status: Accepted

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

# aの合計値がbの合計値を下回る場合は終了
total_a = sum(a)
total_b = sum(b)
if total_a < total_b:
  print(-1)
  exit()
  
# 数列aと数列bの差分を取得  
nums = [0]*n
for i in range(n): nums[i] = a[i] - b[i]
nums.sort()

ans = 0
m = 0
for i in range(n): # 差分がマイナスの値の合計と数を取得
  if nums[i] < 0:
    m += nums[i]
    ans += 1
  else: break

# 差分の大きい値から順にマイナス分を相殺していき、マイナスが終了した時点の変更数を回答する
for i in reversed(range(n)):
  if m >= 0:
    print(ans)
    break
  else:
    m += nums[i]
    ans += 1

Submission status: Accepted

Solution code:
n = int(input())
la = [int(w) for w in input().split()]
lb = [int(w) for w in input().split()]
ld = [a-b for a, b in zip(la, lb)]
if sum(ld) < 0:
    print(-1)
    exit()

llower = [w for w in ld if w < 0]
lupper = [w for w in ld if w > 0]
lowsum = sum(llower)
lupper.sort(reverse=True)

ans = len(llower)

for d in lupper:
    if lowsum >= 0:
        break
    ans += 1
    lowsum += d


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    if sum(a) < sum(b):
        print(-1)
        return

    pos = []
    neg = 0
    for i in range(n):
        x = a[i] - b[i]
        if x >= 0:
            pos.append(x)
        else:
            neg += -x
    pos.sort(reverse=True)
    m = len(pos)
    i = 0
    cur = 0
    while i < m and cur < neg:
        cur += pos[i]
        i += 1
    print(n - len(pos) + i)
    


    
    
    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

R s
S p
P r

"""

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
nega=0
posi=0
yoyu=[]
ans=0
for i in range(N):
  tmp=A[i]-B[i]
  if tmp>=0:
    posi+=tmp
    yoyu.append(tmp)
  else:
    nega+=-1*tmp
    ans+=1
if posi<nega:
  print(-1)
  exit()
elif nega==0:
  print(0)
  exit()

yoyu.sort(reverse=True)
S=0
i=0
while (1):
  S+=yoyu[i]
  if nega<=S:
    ans+=i+1
    print(ans)
    break
  else:
    i+=1

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:
  minus = 0
  plus = []
  for i in range(N):
    dif = A[i] - B[i]
    if dif < 0:
      minus -= dif
    else:
      plus.append(dif)
   
  plus.sort(reverse=True)
  if minus <= 0:
    ans = 0
  else:
    for i in range(len(plus)):
      minus -= plus[i]
      if minus <= 0:
        break
    ans = N-len(plus)+i+1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
d = []
s = 0
for ai, bi in zip(a, b):
    if ai < bi:
        ans += 1
        s += bi - ai
    else:
        d.append(ai - bi)
if ans:
    d.sort(reverse=True)
    ds = 0
    for di in d:
        ds+=di
        ans+=1
        if ds >= s:
            break
    if ds < s:
        print(-1)
    else:
        print(ans)
else:
    print(0)

Submission status: Accepted

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

plus = []
minus = []
for i in range(N):
    tmp = A[i] - B[i]
    if tmp > 0:
        plus.append(tmp)
    elif tmp < 0:
        minus.append(tmp)
        
plus = sorted(plus, reverse=True)

plus_cum = []
for i in range(len(plus)):
    if i == 0:
        plus_cum.append(plus[0])
    else:
        plus_cum.append(plus_cum[i-1] + plus[i])
        
minus_sum = sum(minus)
ans = -1
for i in range(len(plus_cum)):
    if plus_cum[i] >= -minus_sum:
        ans = i+1
        break

if len(minus) == 0:
    print(0)
elif ans == -1:
    print(ans)
else:
    print(ans + len(minus))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c

import sys
n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

for i in range(n):
    if A[i] < B[i]:
        break
else:
    print(0)
    sys.exit()
s = 0
ans = 0
t = []
for i in range(n):
    if A[i] < B[i]:
        s += B[i] - A[i]
        ans += 1
    t.append(A[i] - B[i])
t.sort(reverse=True)

for i in range(n):
    if s < 0:
        break
    s -= t[i]
    ans += 1
if s > 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()))

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    elif A[i] > B[i]: S_ab.append(A[i] - B[i])

ans = len(S_ba)
now = 0
rem = sum(S_ba)
S_ab.sort(reverse=True)

for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1

if rem > sum(S_ab): 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()))

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    # elif A[i] > B[i]: S_ab.append(A[i] - B[i])
    else: S_ab.append(A[i] - B[i])

ans = len(S_ba)
now = 0
rem = sum(S_ba)

S_ab.sort(reverse=True)

if rem > sum(S_ab):
    print(-1)
    exit()
for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1
print(ans)

Submission status: Accepted

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    # elif A[i] > B[i]: S_ab.append(A[i] - B[i])
    else: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
rem = sum(S_ba)
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1

print(ans)