You are given two arrays A and B each of length N. You can perform the following operation on array A zero or more times. 
	Select any two indices i and j, 1 <= i , j <= N and i != j
	Set A[i] = A[i] + 2 and A[j] = A[j]-2 
Find the minimum number of operations required to make A and B equal.
Note :
	Two arrays are said to be equal if the frequency of each element is equal in both of them.
	Arrays may contain duplicate elements.
Example 1:
Input:
N = 3
A[] = {2, 5, 6}
B[] = {1, 2, 10}
Output: 2
Explanation: 
Select i = 3, j = 2, A[3] = 6 + 2 = 8 and A[2] = 5 - 2 = 3
Select i = 3, j = 2, A[3] = 8 + 2 = 10 and A[2] = 3 - 2 = 1
Now A = {2, 1, 10} and B = {1, 2, 10}
Example 2:
Input:
N = 2
A[] = {3, 3}
B[] = {9, 8}
Output: -1
Explanation: 
It can be shown that A cannot be made equal to B.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve() which takes the 2 arrays A[], B[] and their size N as input parameters and returns the minimum number of moves to make A and B equal if possible else return -1.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
-10^{9} <= A[i] <= 10^{9}
-10^{9} <= B[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: from typing import List

class Solution:

    def solve(self, N : int, A : List[int], B : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def solve(self, N: int, a: List[int], b: List[int]) -> int:
		if sum(a) != sum(b):
			return -1
		a.sort()
		b.sort()
		(ae, ao, be, bo) = ([], [], [], [])
		for i in range(N):
			if a[i] % 2:
				ao.append(a[i])
			else:
				ae.append(a[i])
			if b[i] % 2:
				bo.append(b[i])
			else:
				be.append(b[i])
		if len(ao) != len(bo) or len(ae) != len(be):
			return -1
		(osum, esum) = (0, 0)
		for i in range(len(ao)):
			osum += abs(ao[i] - bo[i])
		for i in range(len(ae)):
			esum += abs(ae[i] - be[i])
		if osum % 2 or esum % 2:
			return -1
		else:
			return (osum + esum) // 2 // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		ocnt1 = []
		ocnt2 = []
		ecnt1 = []
		ecnt2 = []
		sm = 0
		for i in range(N):
			sm += A[i] - B[i]
			if A[i] & 1:
				ocnt1.append(A[i])
			else:
				ecnt1.append(A[i])
			if B[i] & 1:
				ocnt2.append(B[i])
			else:
				ecnt2.append(B[i])
		ans = 0
		if len(ocnt1) == len(ocnt2) and sm == 0:
			ocnt1.sort()
			ocnt2.sort()
			ecnt1.sort()
			ecnt2.sort()
			for i in range(len(ocnt1)):
				ans += max(0, ocnt1[i] - ocnt2[i])
			for i in range(len(ecnt2)):
				ans += max(0, ecnt1[i] - ecnt2[i])
			return ans // 2
		else:
			return -1


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		oa = []
		ea = []
		ob = []
		eb = []
		for i in A:
			if i % 2:
				oa.append(i)
			else:
				ea.append(i)
		for i in B:
			if i % 2:
				ob.append(i)
			else:
				eb.append(i)
		if len(oa) != len(ob) or len(ea) != len(eb):
			return -1
		oa.sort()
		ea.sort()
		ob.sort()
		eb.sort()
		ans = 0
		for i in range(len(oa)):
			x = abs(oa[i] - ob[i])
			ans += x // 2
		for i in range(len(eb)):
			x = abs(eb[i] - ea[i])
			ans += x // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, n: int, a: List[int], b: List[int]) -> int:
		(sm, ans, cnt) = (0, -1, 0)
		(odd, even) = ([], [])
		a.sort()
		b.sort()
		for i in range(n):
			if b[i] & 1:
				odd.append(b[i])
			else:
				even.append(b[i])
		x = len(odd) - 1
		y = len(even) - 1
		for i in range(n - 1, -1, -1):
			if a[i] & 1:
				if x < 0:
					return ans
				sm += (a[i] - odd[x]) // 2
				cnt += max(0, (a[i] - odd[x]) // 2)
				x -= 1
			else:
				if y < 0:
					return ans
				sm += (a[i] - even[y]) // 2
				cnt += max(0, (a[i] - even[y]) // 2)
				y -= 1
		if sm != 0:
			return ans
		return cnt


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		sumA = [i % 2 for i in A]
		sumB = [i % 2 for i in B]
		if sum(sumA) != sum(sumB) or sum(A) != sum(B):
			return -1
		(evenA, evenB, oddA, oddB) = ([], [], [], [])
		for (i, j) in zip(A, B):
			if i % 2 == 0:
				evenA.append(i)
			else:
				oddA.append(i)
			if j % 2 == 0:
				evenB.append(j)
			else:
				oddB.append(j)
		evenA.sort()
		evenB.sort()
		oddA.sort()
		oddB.sort()
		counter = 0
		for (i, j) in zip(evenA, evenB):
			if abs(i - j) % 2 != 0:
				return -1
			counter += abs(i - j) // 2
		for (i, j) in zip(oddA, oddB):
			if abs(i - j) % 2 != 0:
				return -1
			counter += abs(i - j) // 2
		return counter // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		A.sort()
		B.sort()
		Aodds = [num for num in A if num % 2 != 0]
		Aevens = [num for num in A if num % 2 == 0]
		Bodds = [num for num in B if num % 2 != 0]
		Bevens = [num for num in B if num % 2 == 0]
		sum1 = sum(A)
		sum2 = sum(B)
		if sum1 != sum2 or len(Aodds) != len(Bodds):
			return -1
		ans = sum((abs(Aodds[i] - Bodds[i]) for i in range(len(Aodds))))
		ans += sum((abs(Aevens[i] - Bevens[i]) for i in range(len(Aevens))))
		return ans // 4


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		A.sort()
		B.sort()
		tsum = 0
		top = 0
		oi = 0
		ei = 0
		flag = 0
		for i in range(N):
			if A[i] % 2 == 0:
				if ei == N:
					flag = 1
					break
				for j in range(ei, N):
					if B[j] % 2 == 0:
						top += abs(A[i] - B[j]) // 2
						tsum += A[i] - B[j]
						break
				ei = j + 1
			else:
				if oi == N:
					flag = 1
					break
				for j in range(oi, N):
					if B[j] % 2 == 1:
						top += abs(A[i] - B[j]) // 2
						tsum += A[i] - B[j]
						break
				oi = j + 1
		if flag == 1 or tsum != 0:
			return -1
		else:
			return top // 2


from typing import List
from bisect import bisect_left

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if not sum(A) == sum(B):
			return -1
		BEvens = [x for x in B if x % 2 == 0]
		AEvens = [x for x in A if x % 2 == 0]
		if not len(AEvens) == len(BEvens):
			return -1
		BOdds = [x for x in B if x % 2 == 1]
		AOdds = [x for x in A if x % 2 == 1]
		AEvens.sort()
		AOdds.sort()
		BEvens.sort()
		BOdds.sort()
		numOperations = 0
		for i in range(len(AEvens)):
			numOperations += abs(AEvens[i] - BEvens[i]) // 2
		for i in range(len(AOdds)):
			numOperations += abs(AOdds[i] - BOdds[i]) // 2
		return numOperations // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		a_even = []
		a_odd = []
		b_even = []
		b_odd = []
		for a in A:
			if a % 2 == 0:
				a_even.append(a)
			else:
				a_odd.append(a)
		for b in B:
			if b % 2 == 0:
				b_even.append(b)
			else:
				b_odd.append(b)
		a_even.sort()
		b_even.sort()
		a_odd.sort()
		b_odd.sort()
		if len(a_odd) != len(b_odd):
			return -1
		sum = 0
		ab_sum = 0
		for i in range(len(a_odd)):
			diff = a_odd[i] - b_odd[i]
			sum += diff
			ab_sum += abs(diff)
		for i in range(len(a_even)):
			diff = a_even[i] - b_even[i]
			sum += diff
			ab_sum += abs(diff)
		if sum != 0:
			return -1
		return ab_sum // 4


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		(sm, cnt, ans) = (0, 0, -1)
		odd = []
		eve = []
		A.sort()
		B.sort()
		for i in range(N):
			if B[i] & 1:
				odd.append(B[i])
			else:
				eve.append(B[i])
		x = len(odd) - 1
		y = len(eve) - 1
		for i in range(N - 1, -1, -1):
			if A[i] & 1:
				if x < 0:
					return ans
				sm += (A[i] - odd[x]) // 2
				cnt += max(0, (A[i] - odd[x]) // 2)
				x -= 1
			else:
				if y < 0:
					return ans
				sm += (A[i] - eve[y]) // 2
				cnt += max(0, (A[i] - eve[y]) // 2)
				y -= 1
		if sm != 0:
			return ans
		return cnt


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		A.sort()
		B.sort()
		odd_A = [i for i in A if i % 2 != 0]
		odd_B = [i for i in B if i % 2 != 0]
		if len(odd_A) != len(odd_B):
			return -1
		even_A = [i for i in A if i % 2 == 0]
		even_B = [i for i in B if i % 2 == 0]
		if len(even_A) != len(even_B):
			return -1
		diff_sum = 0
		for (oa, ob) in zip(odd_A, odd_B):
			diff_sum += abs(oa - ob) // 2
		for (ea, eb) in zip(even_A, even_B):
			diff_sum += abs(ea - eb) // 2
		return diff_sum // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		odds = eves = 0
		for i in A:
			if i & 1:
				odds += 1
			else:
				eves += 1
		for i in B:
			if i & 1:
				odds -= 1
			else:
				eves -= 1
		if odds != 0 or eves != 0:
			return -1
		a_odds = []
		a_eves = []
		for i in A:
			if i & 1:
				a_odds.append(i)
			else:
				a_eves.append(i)
		a_odds.sort()
		a_eves.sort()
		b_odds = []
		b_eves = []
		for i in B:
			if i & 1:
				b_odds.append(i)
			else:
				b_eves.append(i)
		b_odds.sort()
		b_eves.sort()
		minm = maxm = 0
		for i in range(len(a_odds)):
			if a_odds[i] > b_odds[i]:
				minm += (a_odds[i] - b_odds[i]) // 2
			else:
				maxm += (b_odds[i] - a_odds[i]) // 2
		for i in range(len(a_eves)):
			if a_eves[i] > b_eves[i]:
				minm += (a_eves[i] - b_eves[i]) // 2
			else:
				maxm += (b_eves[i] - a_eves[i]) // 2
		return maxm if maxm == minm else -1


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		A.sort()
		B.sort()
		A_odd = []
		B_odd = []
		A_even = []
		B_even = []
		for i in range(N):
			if A[i] % 2 != 0:
				A_odd.append(A[i])
			else:
				A_even.append(A[i])
			if B[i] % 2 != 0:
				B_odd.append(B[i])
			else:
				B_even.append(B[i])
		if sum(A) != sum(B) or len(B_odd) != len(A_odd):
			return -1
		ans = 0
		for i in range(len(A_odd)):
			ans += abs(A_odd[i] - B_odd[i])
		for i in range(len(A_even)):
			ans += abs(A_even[i] - B_even[i])
		return ans // 4


from typing import List

class Solution:

	def solve(self, N: int, a: List[int], b: List[int]) -> int:
		ea = []
		eb = []
		oa = []
		ob = []
		for i in range(N):
			if a[i] % 2 == 0:
				ea.append(a[i])
			else:
				oa.append(a[i])
			if b[i] % 2 == 0:
				eb.append(b[i])
			else:
				ob.append(b[i])
		if sum(a) != sum(b) or len(oa) != len(ob) or len(ea) != len(eb):
			return -1
		ans = 0
		s = [oa, ob, ea, eb]
		for i in s:
			i.sort()
		for i in range(len(ea)):
			ans += abs(ea[i] - eb[i])
		for i in range(len(oa)):
			ans += abs(oa[i] - ob[i])
		return int(ans / 4)


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		s1 = s2 = 0
		Aeo = [[], []]
		Beo = [[], []]
		for i in range(N):
			s1 += A[i]
			s2 += B[i]
			if abs(A[i]) % 2 == 0:
				Aeo[0].append(A[i])
			else:
				Aeo[1].append(A[i])
			if abs(B[i]) % 2 == 0:
				Beo[0].append(B[i])
			else:
				Beo[1].append(B[i])
		if s1 != s2 or len(Aeo[0]) != len(Beo[0]):
			return -1
		ans = 0
		for i in range(2):
			Aeo[i].sort()
			Beo[i].sort()
			for j in range(len(Aeo[i])):
				ans += abs(Aeo[i][j] - Beo[i][j]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		AEvenOdd = [[], []]
		BEvenOdd = [[], []]
		sum1 = 0
		sum2 = 0
		for i in range(N):
			sum1 += A[i]
			sum2 += B[i]
			if abs(A[i]) % 2 == 0:
				AEvenOdd[0].append(A[i])
			else:
				AEvenOdd[1].append(A[i])
			if abs(B[i]) % 2 == 0:
				BEvenOdd[0].append(B[i])
			else:
				BEvenOdd[1].append(B[i])
		if sum1 != sum2 or len(AEvenOdd[0]) != len(BEvenOdd[0]):
			return -1
		ans = 0
		for i in range(2):
			AEvenOdd[i].sort()
			BEvenOdd[i].sort()
			for j in range(len(AEvenOdd[i])):
				ans += abs(AEvenOdd[i][j] - BEvenOdd[i][j]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		summ = 0
		comparison = 0
		(evenA, oddA, evenB, oddB) = ([], [], [], [])
		A.sort()
		B.sort()
		for i in range(N):
			summ += A[i] - B[i]
			if A[i] % 2 == 0:
				evenA.append(A[i])
			else:
				oddA.append(A[i])
			if B[i] % 2 == 0:
				evenB.append(B[i])
			else:
				oddB.append(B[i])
		if summ != 0 or len(oddA) != len(oddB):
			return -1
		for i in range(len(evenA)):
			comparison += abs(evenA[i] - evenB[i]) // 2
		for i in range(len(oddA)):
			comparison += abs(oddA[i] - oddB[i]) // 2
		return comparison // 2


from typing import List

class Solution:

	def solve(self, N: int, a: List[int], b: List[int]) -> int:
		if sum(a) != sum(b):
			return -1
		even_a = [[], []]
		even_b = [[], []]
		for i in range(len(a)):
			if a[i] % 2 == 0:
				even_a[0].append(a[i])
			else:
				even_a[1].append(a[i])
		for i in range(len(b)):
			if b[i] % 2 == 0:
				even_b[0].append(b[i])
			else:
				even_b[1].append(b[i])
		if len(even_a[0]) != len(even_b[0]):
			return -1
		ans = 0
		for i in range(2):
			even_a[i].sort()
			even_b[i].sort()
			for j in range(len(even_a[i])):
				ans += abs(even_a[i][j] - even_b[i][j]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:

		def get_even_odd_arrs(arr):
			arr_odd = []
			arr_even = []
			for num in arr:
				if num % 2:
					arr_odd.append(num)
				else:
					arr_even.append(num)
			arr_odd.sort()
			arr_even.sort()
			return (arr_odd, arr_even)
		(a_odd, a_even) = get_even_odd_arrs(A)
		(b_odd, b_even) = get_even_odd_arrs(B)
		if len(a_odd) != len(b_odd) or len(a_even) != len(b_even):
			return -1
		count_add = 0
		count_sub = 0
		for (i, a_num) in enumerate(a_odd):
			b_num = b_odd[i]
			if a_num < b_num:
				count_add += (b_num - a_num) // 2
			elif a_num > b_num:
				count_sub += (a_num - b_num) // 2
		for (i, a_num) in enumerate(a_even):
			b_num = b_even[i]
			if a_num < b_num:
				count_add += (b_num - a_num) // 2
			elif a_num > b_num:
				count_sub += (a_num - b_num) // 2
		if count_add != count_sub:
			return -1
		return count_add


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		mod_A = [[], []]
		mod_B = [[], []]
		total_sum = 0
		n = len(A)
		for i in range(n):
			total_sum += A[i] - B[i]
			mod_A[A[i] % 2].append(A[i])
			mod_B[B[i] % 2].append(B[i])
		if total_sum != 0 or len(mod_A[0]) != len(mod_B[0]) or len(mod_A[1]) != len(mod_B[1]):
			return -1
		ans = 0
		for i in range(2):
			mod_A[i].sort()
			mod_B[i].sort()
			for j in range(len(mod_A[i])):
				ans += abs(mod_A[i][j] - mod_B[i][j]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		else:
			ca = 0
			cb = 0
			for i in A:
				if i % 2 == 0:
					ca += 1
			for i in B:
				if i % 2 == 0:
					cb += 1
			if ca != cb:
				return -1
			A.sort()
			B.sort()
			A1 = []
			A2 = []
			for i in A:
				if i % 2 == 0:
					A1.append(i)
				else:
					A2.append(i)
			B1 = []
			B2 = []
			for i in B:
				if i % 2 == 0:
					B1.append(i)
				else:
					B2.append(i)
			ans = 0
			for i in range(len(A1)):
				ans += abs(A1[i] - B1[i]) // 2
			for i in range(len(A2)):
				ans += abs(A2[i] - B2[i]) // 2
			return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		A.sort()
		B.sort()
		Ao = []
		Ae = []
		Bo = []
		Be = []
		for i in range(N):
			if A[i] % 2 == 1:
				Ao.append(A[i])
			else:
				Ae.append(A[i])
			if B[i] % 2 == 1:
				Bo.append(B[i])
			else:
				Be.append(B[i])
		if len(Ao) != len(Bo) or len(Ae) != len(Be):
			return -1
		d = 0
		c = 0
		for i in range(len(Ao)):
			c += abs(Ao[i] - Bo[i]) // 2
		for i in range(len(Be)):
			c += abs(Ae[i] - Be[i]) // 2
		return c // 2


from typing import List

class Solution:

	def solve(self, n: int, a: List[int], b: List[int]) -> int:
		summ_a = sum(a)
		summ_b = sum(b)
		if summ_a != summ_b:
			return -1
		a.sort()
		b.sort()
		(a_ev, a_odd, b_ev, b_odd) = ([], [], [], [])
		for i in range(0, len(a)):
			if a[i] % 2 != 0:
				a_odd.append(a[i])
			if a[i] % 2 == 0:
				a_ev.append(a[i])
			if b[i] % 2 != 0:
				b_odd.append(b[i])
			if b[i] % 2 == 0:
				b_ev.append(b[i])
		if len(a_ev) != len(b_ev) or len(a_odd) != len(b_odd):
			return -1
		count = 0
		for k in range(0, len(a_ev)):
			count += abs(a_ev[k] - b_ev[k])
		for j in range(0, len(a_odd)):
			count += abs(a_odd[j] - b_odd[j])
		return count // 4


from typing import List

class Solution:

	def solve(self, n: int, a: List[int], b: List[int]) -> int:
		a.sort()
		b.sort()
		a_even = []
		a_odd = []
		b_even = []
		b_odd = []
		sum1 = 0
		sum2 = 0
		for i in range(n):
			sum1 += a[i]
			sum2 += b[i]
			if a[i] % 2 != 0:
				a_odd.append(a[i])
			else:
				a_even.append(a[i])
			if b[i] % 2 != 0:
				b_odd.append(b[i])
			else:
				b_even.append(b[i])
		if sum1 != sum2 or len(a_odd) != len(b_odd):
			return -1
		ans = 0
		for i in range(len(a_even)):
			ans = ans + abs(a_even[i] - b_even[i])
		for i in range(len(a_odd)):
			ans = ans + abs(a_odd[i] - b_odd[i])
		return ans // 4


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		A.sort()
		B.sort()
		(evens_A, odds_A) = ([], [])
		(evens_B, odds_B) = ([], [])
		(sum_A, sum_B) = (sum(A), sum(B))
		for (ele_A, ele_B) in zip(A, B):
			if ele_A & 1:
				odds_A.append(ele_A)
			else:
				evens_A.append(ele_A)
			if ele_B & 1:
				odds_B.append(ele_B)
			else:
				evens_B.append(ele_B)
		if sum_A != sum_B or len(evens_A) != len(evens_B):
			return -1
		ops = 0
		for (ea, eb) in zip(evens_A, evens_B):
			ops += abs(ea - eb) >> 1
		for (oa, ob) in zip(odds_A, odds_B):
			ops += abs(oa - ob) >> 1
		A.sort()
		B.sort()
		(evens_A, odds_A) = ([], [])
		(evens_B, odds_B) = ([], [])
		(sum_A, sum_B) = (sum(A), sum(B))
		for (ele_A, ele_B) in zip(A, B):
			if ele_A & 1:
				odds_A.append(ele_A)
			else:
				evens_A.append(ele_A)
			if ele_B & 1:
				odds_B.append(ele_B)
			else:
				evens_B.append(ele_B)
		if sum_A != sum_B or len(evens_A) != len(evens_B):
			return -1
		ops = 0
		for (ea, eb) in zip(evens_A, evens_B):
			ops += abs(ea - eb) >> 1
		for (oa, ob) in zip(odds_A, odds_B):
			ops += abs(oa - ob) >> 1
		return ops >> 1


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		sa = sum(A)
		sb = sum(B)
		if sa != sb:
			return -1
		else:
			A.sort()
			B.sort()
			(pea, peb, poa, pob) = ([], [], [], [])
			for i in range(N):
				if A[i] % 2 == 0:
					pea.append(A[i])
				else:
					poa.append(A[i])
				if B[i] % 2 == 0:
					peb.append(B[i])
				else:
					pob.append(B[i])
			if len(pea) != len(peb):
				return -1
			else:
				c = 0
				for i in range(len(pea)):
					if pea[i] > peb[i]:
						c += pea[i] - peb[i]
				for i in range(len(poa)):
					if poa[i] > pob[i]:
						c += poa[i] - pob[i]
				return c // 2


from typing import List
from collections import defaultdict

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		ssum = 0
		ap = defaultdict(list)
		bp = defaultdict(list)
		for i in range(N):
			ssum += A[i] - B[i]
			ap[abs(A[i]) % 2].append(A[i])
			bp[abs(B[i]) % 2].append(B[i])
		if ssum != 0 or int(len(ap[0])) != int(len(bp[0])):
			return -1
		ans = 0
		for i in range(2):
			ap[i].sort()
			bp[i].sort()
			for j in range(len(ap[i])):
				ans += abs(ap[i][j] - bp[i][j]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		aea = []
		eca = []
		aeb = []
		ecb = []
		for i in A:
			if i % 2:
				aea.append(i)
			else:
				eca.append(i)
		for j in B:
			if j % 2:
				aeb.append(j)
			else:
				ecb.append(j)
		if len(aea) != len(aeb) or len(eca) != len(ecb):
			return -1
		aea.sort()
		eca.sort()
		aeb.sort()
		ecb.sort()
		res = 0
		for i in range(len(aea)):
			x = abs(aea[i] - aeb[i])
			res += x // 2
		for i in range(len(ecb)):
			x = abs(ecb[i] - eca[i])
			res += x // 2
		return res // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		sum1 = sum2 = 0
		(odd1, odd2, even1, even2) = ([], [], [], [])
		for i in range(N):
			if A[i] % 2 == 0:
				even1.append(A[i])
			else:
				odd1.append(A[i])
			sum1 += A[i]
		for i in range(N):
			if B[i] % 2 == 0:
				even2.append(B[i])
			else:
				odd2.append(B[i])
			sum2 += B[i]
		if sum1 != sum2 or len(odd1) != len(odd2):
			return -1
		odd1.sort()
		odd2.sort()
		even1.sort()
		even2.sort()
		ans = 0
		for i in range(len(odd1)):
			ans += abs(odd1[i] - odd2[i])
		for i in range(len(even1)):
			ans += abs(even1[i] - even2[i])
		return ans // 4


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		(ea, eb, oa, ob) = ([], [], [], [])
		for i in A:
			if i % 2 == 0:
				ea.append(i)
			else:
				oa.append(i)
		for i in B:
			if i % 2 == 0:
				eb.append(i)
			else:
				ob.append(i)
		if len(ea) != len(eb) or len(oa) != len(ob):
			return -1
		s = 0
		s2 = 0
		ea.sort()
		eb.sort()
		oa.sort()
		ob.sort()
		for i in range(len(ea)):
			s += ea[i] - eb[i]
			s2 += max(0, ea[i] - eb[i])
		for i in range(len(oa)):
			s += oa[i] - ob[i]
			s2 += max(0, oa[i] - ob[i])
		if s != 0:
			return -1
		return s2 // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		a_odds = []
		b_odds = []
		a_evens = []
		b_evens = []
		max_diff = 0
		for i in range(N):
			if A[i] % 2:
				a_odds.append(A[i])
			else:
				a_evens.append(A[i])
			if B[i] % 2:
				b_odds.append(B[i])
			else:
				b_evens.append(B[i])
		if len(a_odds) != len(b_odds) or len(a_evens) != len(b_evens):
			return -1
		a_odds.sort()
		b_odds.sort()
		a_evens.sort()
		b_evens.sort()
		total = 0
		for i in range(len(a_odds)):
			x = abs(a_odds[i] - b_odds[i])
			total += x // 2
		for i in range(len(a_evens)):
			x = abs(a_evens[i] - b_evens[i])
			total += x // 2
		return total // 2

	def solve_v2(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		oa = []
		ea = []
		ob = []
		eb = []
		for i in A:
			if i % 2:
				oa.append(i)
			else:
				ea.append(i)
		for i in B:
			if i % 2:
				ob.append(i)
			else:
				eb.append(i)
		if len(oa) != len(ob) or len(ea) != len(eb):
			return -1
		oa.sort()
		ea.sort()
		ob.sort()
		eb.sort()
		ans = 0
		for i in range(len(oa)):
			x = abs(oa[i] - ob[i])
			ans += x // 2
		for i in range(len(eb)):
			x = abs(eb[i] - ea[i])
			ans += x // 2
		return ans // 2

	def solve_v1(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		a_odds = []
		b_odds = []
		a_evens = []
		b_evens = []
		max_diff = 0
		for i in range(N):
			if A[i] % 2:
				a_odds.append(A[i])
			else:
				a_evens.append(A[i])
			if B[i] % 2:
				b_odds.append(B[i])
			else:
				b_evens.append(B[i])
		if len(a_odds) != len(b_odds) or len(a_evens) != len(b_evens):
			return -1
		o_diff = abs(sum(b_odds) - sum(a_odds))
		e_diff = abs(sum(b_evens) - sum(a_evens))
		max_diff = max(o_diff, e_diff)
		return max_diff // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		evens1 = []
		evens2 = []
		odds1 = []
		odds2 = []
		for i in range(N):
			if A[i] & 1:
				odds1.append(A[i])
			else:
				evens1.append(A[i])
			if B[i] & 1:
				odds2.append(B[i])
			else:
				evens2.append(B[i])
		if len(evens1) != len(evens2) or len(odds1) != len(odds2):
			return -1
		evens1.sort()
		evens2.sort()
		odds1.sort()
		odds2.sort()
		add = 0
		sub = 0
		for i in range(len(evens1)):
			if evens1[i] >= evens2[i]:
				add += abs(evens1[i] - evens2[i]) // 2
			else:
				sub += abs(evens1[i] - evens2[i]) // 2
		for i in range(len(odds1)):
			if odds1[i] >= odds2[i]:
				add += abs(odds1[i] - odds2[i]) // 2
			else:
				sub += abs(odds1[i] - odds2[i]) // 2
		if add != sub:
			return -1
		return add


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		Aodd = []
		Aeven = []
		Bodd = []
		Beven = []
		for i in A:
			if i % 2:
				Aodd.append(i)
			else:
				Aeven.append(i)
		for i in B:
			if i % 2:
				Bodd.append(i)
			else:
				Beven.append(i)
		if len(Aodd) != len(Bodd) or len(Aeven) != len(Beven):
			return -1
		Aodd.sort()
		Aeven.sort()
		Bodd.sort()
		Beven.sort()
		ans = 0
		for i in range(len(Aodd)):
			x = abs(Aodd[i] - Bodd[i])
			ans += x // 2
		for i in range(len(Beven)):
			x = abs(Beven[i] - Aeven[i])
			ans += x // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		(ea, eb, oa, ob) = ([], [], [], [])
		for i in range(N):
			if A[i] % 2 == 0:
				ea.append(A[i])
			else:
				oa.append(A[i])
			if B[i] % 2 == 0:
				eb.append(B[i])
			else:
				ob.append(B[i])
		if len(oa) != len(ob) or len(ea) != len(eb):
			return -1
		for e in [oa, ob, ea, eb]:
			e.sort()
		a = oa + ea
		b = ob + eb
		(v, cnt) = (0, 0)
		for i in range(len(a)):
			d = a[i] - b[i]
			if d > 0:
				cnt += d // 2
			v += d
		if v != 0:
			return -1
		return cnt


from typing import List

class Solution:

	def solve(self, n: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		A.sort()
		B.sort()
		even_A = []
		odd_A = []
		for i in range(n):
			if A[i] % 2 == 0:
				even_A.append(A[i])
			else:
				odd_A.append(A[i])
		even_B = []
		odd_B = []
		for i in range(n):
			if B[i] % 2 == 0:
				even_B.append(B[i])
			else:
				odd_B.append(B[i])
		if len(even_A) != len(even_B) or len(odd_A) != len(odd_B):
			return -1
		ans = 0
		for i in range(len(even_A)):
			ans += abs(even_A[i] - even_B[i]) // 2
		for i in range(len(odd_A)):
			ans += abs(odd_A[i] - odd_B[i]) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		sum1 = 0
		A.sort()
		B.sort()
		(a, b, c, d) = ([], [], [], [])
		for i in range(len(A)):
			sum1 += A[i] - B[i]
			if A[i] % 2 != 0:
				a.append(A[i])
			else:
				b.append(A[i])
			if B[i] % 2 != 0:
				c.append(B[i])
			else:
				d.append(B[i])
		if sum1 != 0 or len(a) != len(c):
			return -1
		opr = 0
		for i in range(len(a)):
			diff = abs(a[i] - c[i])
			opr += diff // 2
		for i in range(len(b)):
			diff = abs(b[i] - d[i])
			opr += diff // 2
		return opr // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		count = 0
		A.sort()
		B.sort()
		if sum(A) != sum(B):
			return -1
		(Aevenodd, Bevenodd) = ([[], []], [[], []])
		for i in range(N):
			Aevenodd[A[i] % 2].append(A[i])
			Bevenodd[B[i] % 2].append(B[i])
		(countaeven, countaodd, countbeven, countbodd) = (len(Aevenodd[0]), len(Aevenodd[1]), len(Bevenodd[0]), len(Bevenodd[1]))
		if countaeven != countbeven and countaodd != countbodd:
			return -1
		for i in range(countaeven):
			count = count + abs(Aevenodd[0][i] - Bevenodd[0][i]) // 2
		for i in range(countbodd):
			count = count + abs(Aevenodd[1][i] - Bevenodd[1][i]) // 2
		return count // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		if sum((i & 1 for i in A)) != sum((i & 1 for i in B)):
			return -1
		A = sorted(A)
		B = sorted(B)
		oddsA = [i for i in A if i & 1]
		evenA = [i for i in A if not i & 1]
		oddsB = [i for i in B if i & 1]
		evenB = [i for i in B if not i & 1]
		posx = sum((oddsA[i] - oddsB[i] for i in range(len(oddsA)) if oddsA[i] > oddsB[i]))
		negx = -sum((oddsA[i] - oddsB[i] for i in range(len(oddsA)) if oddsA[i] < oddsB[i]))
		posy = sum((evenA[i] - evenB[i] for i in range(len(evenA)) if evenA[i] > evenB[i]))
		negy = -sum((evenA[i] - evenB[i] for i in range(len(evenA)) if evenA[i] < evenB[i]))
		if posx + posy != negx + negy:
			return -1
		return posx + posy >> 1


from typing import List
from collections import Counter

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		A.sort()
		B.sort(reverse=True)
		numMoves = 0
		sumDiffs = 0
		odd = []
		even = []
		for i in range(N):
			if B[i] % 2 == 0:
				even.append(B[i])
			else:
				odd.append(B[i])
		for i in range(N):
			if A[i] % 2 == 0:
				if len(even) == 0:
					return -1
				sumDiffs += even[-1] - A[i]
				numMoves += abs(even[-1] - A[i]) // 2
				even.pop()
			else:
				if len(odd) == 0:
					return -1
				sumDiffs += odd[-1] - A[i]
				numMoves += abs(odd[-1] - A[i]) // 2
				odd.pop()
		if sumDiffs != 0:
			return -1
		return numMoves // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		(oddA, oddB, evenA, evenB) = ([], [], [], [])
		(sum1, sum2) = (0, 0)
		for (numA, numB) in zip(A, B):
			sum1 += numA
			sum2 += numB
			if numA % 2 == 0:
				evenA.append(numA)
			else:
				oddA.append(numA)
			if numB % 2 == 0:
				evenB.append(numB)
			else:
				oddB.append(numB)
		if sum1 != sum2 or len(evenA) != len(evenB):
			return -1
		(oddA.sort(), evenA.sort(), oddB.sort(), evenB.sort())
		ans = 0
		for (numA, numB) in zip(evenA, evenB):
			ans += abs(numA - numB) // 2
		for (numA, numB) in zip(oddA, oddB):
			ans += abs(numA - numB) // 2
		return ans // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		Even = [[] for i in range(2)]
		Odd = [[] for i in range(2)]
		total = 0
		res = 0
		for i in range(len(A)):
			total += A[i] - B[i]
			if A[i] & 1 == 0:
				Even[0].append(A[i])
			else:
				Odd[0].append(A[i])
			if B[i] & 1 == 0:
				Even[1].append(B[i])
			else:
				Odd[1].append(B[i])
		if total != 0 or len(Even[0]) != len(Even[1]):
			return -1
		Even[0].sort()
		Even[1].sort()
		Odd[0].sort()
		Odd[1].sort()
		for i in range(len(Even[0])):
			res += abs(Even[0][i] - Even[1][i]) // 2
		for i in range(len(Odd[0])):
			res += abs(Odd[0][i] - Odd[1][i]) // 2
		return res // 2


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if len(A) != N or len(B) != N:
			return -1
		As = sorted(A)
		Bs = sorted(B)
		ase = [x for x in As if x % 2 == 0]
		bse = [x for x in Bs if x % 2 == 0]
		aso = [x for x in As if x % 2 != 0]
		bso = [x for x in Bs if x % 2 != 0]
		if len(aso) != len(bso):
			return -1
		opcount = 0
		carry = 0
		for diff in (a - b for (a, b) in zip(aso, bso)):
			carry += diff
			if diff > 0:
				if carry > 0:
					opcount += min(carry, diff) // 2
			elif diff < 0:
				if carry < 0:
					opcount += max(carry, diff) // -2
		for diff in (a - b for (a, b) in zip(ase, bse)):
			carry += diff
			if diff > 0:
				if carry > 0:
					opcount += min(carry, diff) // 2
			elif diff < 0:
				if carry < 0:
					opcount += max(carry, diff) // -2
		return opcount if carry == 0 else -1


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		if sum(A) != sum(B):
			return -1
		(AEven, BEven) = ([], [])
		(AOdd, BOdd) = ([], [])
		for i in range(N):
			if abs(A[i]) & 1 == 0:
				AEven.append(A[i])
			else:
				AOdd.append(A[i])
			if abs(B[i]) & 1 == 0:
				BEven.append(B[i])
			else:
				BOdd.append(B[i])
		if len(AEven) != len(BEven):
			return -1
		AEven.sort()
		BEven.sort()
		AOdd.sort()
		BOdd.sort()
		ans = 0
		for i in range(len(AEven)):
			ans += abs(AEven[i] - BEven[i])
		for i in range(len(AOdd)):
			ans += abs(AOdd[i] - BOdd[i])
		return ans // 4


from typing import List

class Solution:

	def solve(self, N: int, A: List[int], B: List[int]) -> int:
		sum_val = 0
		(AP, BP) = ([[], []], [[], []])
		for i in range(N):
			sum_val += A[i] - B[i]
			AP[abs(A[i]) % 2].append(A[i])
			BP[abs(B[i]) % 2].append(B[i])
		if sum_val != 0 or len(AP[0]) != len(BP[0]):
			return -1
		ans = 0
		for i in range(2):
			AP[i].sort()
			BP[i].sort()
			for j in range(len(AP[i])):
				ans += abs(AP[i][j] - BP[i][j]) // 2
		return ans // 2