Given two arrays A[] and B[] of same length N. There are N types of sticks of lengths specified. Each stick of length A[i] is present in B[i] units (i=1 to N). You have to construct the squares and rectangles using these sticks. Each unit of a stick can be used as length or breadth of a rectangle or as a side of square. A single unit of a stick can be used only once.
Let S be the sum of lengths of all sticks that are used in constructing squares and rectangles. The task is to calculate the maximum possible value of S.
Note: The element in array A[] is always unique.
Example 1:
Input:
N = 4
A[] = {3,4,6,5}
B[] = {2,3,1,6}
Output: 
38
Explanation: 
There are 2 sticks of length 3.
There are 3 sticks of length 4.
There is a 1 stick of length 6.
There are 6 sticks of length 5.
One square can be made using 4 sticks of
4th kind (5*4=20)
A rectangle can be made using 2 sticks of 
4th kind and 2 sticks of 2nd kind (5*2+4*2=18)
S = 20 + 18 = 38
Example 2:
Input:
N = 1
A[] = {3}
B[] = {2}
Output: 
0
Explanation: 
There are only 2 sticks of length 3 which are 
not enough to make the square or rectangle.
Your Task: 
You don't need to read input or print anything. Complete the function maxPossibleValue( ) which takes the integer N, the array A[], and the array B[] as input parameters and returns the maximum possible value of S. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ A[] ≤ 10^{6}
1 ≤ B[] ≤ 10^{2}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:

    def maxPossibleValue(self, N, A, B): 

        #code here



Solutions:
class Solution:

	def maxPossibleValue(self, N, A, B):
		ts = 0
		ans = 0
		m = 1000000007
		for i in range(N):
			if B[i] // 2 > 0:
				ans += 2 * (B[i] // 2) * A[i]
				ts += B[i] // 2
				m = min(m, A[i])
		if ts % 2 != 0:
			ans -= 2 * m
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		sides = 0
		peri = 0
		mn = float('inf')
		for i in range(N):
			if B[i] % 2 == 1:
				B[i] -= 1
			sides += B[i]
			peri += A[i] * B[i]
			if B[i]:
				mn = min(mn, A[i])
		if sides % 4 != 0:
			peri -= 2 * mn
		return peri


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		c = 0
		mi = 10 ** 10
		for i in range(N):
			if B[i] // 2 > 0:
				ans += 2 * (B[i] // 2) * A[i]
				c += B[i] // 2
				mi = min(mi, A[i])
		if c % 2 == 1:
			ans -= 2 * mi
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		total_sticks = 0
		nm = 99999
		for i in range(N):
			l = A[i]
			r = B[i]
			if r % 2 != 0:
				r -= 1
			if r >= 2:
				nm = min(nm, l)
			ans += l * r
			total_sticks += r
		if total_sticks % 4 != 0:
			ans -= 2 * nm
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		tiny = 1000001
		totalN = 0
		totalL = 0
		for i in range(N):
			if B[i] > 1:
				tiny = min(tiny, A[i])
				totalN += B[i] // 2 * 2
				totalL += A[i] * (B[i] // 2) * 2
		if totalN % 4 == 0:
			return totalL
		else:
			return totalL - 2 * tiny


class Solution:

	def maxPossibleValue(self, N, A, B):
		count = 0
		min_len = float('inf')
		ans = 0
		for i in range(N):
			if B[i] > 1:
				num_rects = B[i] // 2
				min_len = min(min_len, A[i])
				ans += A[i] * num_rects * 2
				count += num_rects
		if count % 2 != 0:
			ans -= min_len * 2
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		tot = 0
		mn = 10 ** 9
		for i in range(N):
			x = A[i]
			y = B[i]
			if y % 2:
				y -= 1
			if y >= 2:
				mn = min(mn, x)
			ans += y * x
			tot += y
		if tot % 4 != 0:
			ans -= 2 * mn
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		if sum(B) < 4:
			return 0
		for i in range(N):
			if B[i] % 2 != 0:
				B[i] -= 1
		if sum(B) < 4:
			return 0
		if sum(B) % 4 == 0:
			summ = 0
			for j in range(N):
				summ += A[j] * B[j]
		else:
			summ = 0
			minn = float('inf')
			for j in range(N):
				summ += A[j] * B[j]
				if B[j] != 0 and minn > A[j] * 2:
					minn = A[j] * 2
			summ -= minn
		return summ


class Solution:

	def maxPossibleValue(self, N, A, B):
		if sum(B) < 4:
			return 0
		mini = 9999999999
		ans = 0
		total = 0
		for i in range(N):
			length = A[i]
			cnt = B[i]
			if cnt % 2 == 1:
				cnt -= 1
			if cnt >= 2:
				ans += length * cnt
				total += cnt
				mini = min(mini, length)
		if total % 4 != 0:
			ans = ans - 2 * mini
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		ele = 0
		mn = 10000000000
		for i in range(N):
			if B[i] % 2 != 0:
				B[i] = B[i] - 1
			if B[i] != 0:
				ans += B[i] * A[i]
				mn = min(mn, A[i])
				ele += B[i]
		if ele % 4 == 2:
			ans = ans - 2 * mn
		return ans


import sys

class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		pv = 0
		mn = sys.maxsize
		for i in range(0, N):
			side = A[i]
			fre = B[i] // 4
			ans += 4 * side * fre
			if B[i] != 1:
				mn = min(side, mn)
			if B[i] % 4 == 2 or B[i] % 4 == 3:
				if pv == 0:
					pv = side
				else:
					ans += 2 * pv + 2 * side
					pv = 0
		if pv != 0:
			ans = max(ans, ans - 2 * mn + 2 * pv)
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		sticks = 0
		minimum = A[0]
		for i in range(len(B)):
			temp = B[i] // 2
			if temp > 0:
				minimum = min(minimum, A[i])
				sticks += temp * 2
				ans += temp * 2 * A[i]
		rem = sticks % 4
		return ans - rem * minimum


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		count = 0
		mini = 1000000000.0
		for i in range(0, N):
			if B[i] > 1:
				quo = B[i] // 4
				rem = B[i] % 4
				if quo > 0:
					ans += A[i] * 4 * quo
					count += 4 * quo
					mini = min(mini, A[i])
				if rem > 1:
					count += 2
					mini = min(mini, A[i])
					ans += A[i] * 2
		if count % 4 != 0:
			ans -= mini * 2
		return ans


class Solution:

	def maxPossibleValue(self, n, a, b):
		t = 0
		p = []
		r = []
		s = 0
		w = 1563738393938393476483
		for i in range(0, n):
			if b[i] >= 2 and b[i] % 2 == 0:
				t = t + a[i] * b[i]
				s = s + b[i]
				w = min(w, a[i])
			elif b[i] >= 2:
				t = t + a[i] * (b[i] - 1)
				s = s + b[i] - 1
				w = min(w, a[i])
				r.append(b[i - 1])
				p.append(a[i] * (b[i] - 1))
		if s % 4 == 0:
			return t
		else:
			return t - 2 * w


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		count = 0
		mini = 10 ** 10
		for i in range(N):
			if B[i] % 2 != 0:
				B[i] -= 1
			count += B[i]
			if B[i] > 0:
				mini = min(mini, A[i])
			ans += A[i] * B[i]
		if count % 4 != 0:
			ans -= mini * 2
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		sticks = []
		max_sticks = 0
		total = 0
		min_len = 0
		for i in range(N):
			if B[i] > 1:
				if B[i] % 2:
					max_sticks += B[i] - 1
					total += A[i] * (B[i] - 1)
				else:
					max_sticks += B[i]
					total += A[i] * B[i]
				if A[min_len] > A[i]:
					min_len = i
		remaining = max_sticks % 4
		if remaining:
			total -= A[min_len] * remaining
		return total


import math

class Solution:

	def maxPossibleValue(self, N, A, B):
		mini = math.inf
		fsum = 0
		count = 0
		for i in range(N):
			if B[i] % 2 != 0:
				B[i] -= 1
		for i in range(N):
			if B[i] >= 2:
				mini = min(mini, A[i])
			fsum += A[i] * B[i]
			count += B[i]
		if count % 4 == 0:
			return fsum
		else:
			return fsum - count % 4 * mini


class Solution:

	def maxPossibleValue(self, N, A, B):
		total = 0
		mn = 1000000
		for i in range(N):
			if B[i] % 2 == 1:
				B[i] = B[i] - 1
			if B[i] != 0:
				total = total + B[i] * A[i]
				mn = min(mn, A[i])
		if sum(B) % 4 == 2:
			total = total - 2 * mn
		return total


from collections import defaultdict

class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		g = [(i, j) for (i, j) in zip(A, B)]
		ans = 0
		prev = -1
		m = 10 ** 15
		for (l, cc) in g:
			c = cc
			if c != 1:
				m = min(m, l)
			if c >= 4:
				ans += 4 * l * (c // 4)
				c -= 4 * (c // 4)
			if c >= 2:
				if prev == -1:
					prev = l
				else:
					ans += l * 2 + prev * 2
					prev = -1
		if prev != -1:
			ans = ans - 2 * m + 2 * prev
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		minLen = float('inf')
		totaLen = 0
		maxLen = 0
		for i in range(N):
			if B[i] > 1:
				maxCnt = B[i] // 2
				totaLen += maxCnt * 2 * A[i]
				maxLen += maxCnt
				if A[i] < minLen:
					minLen = A[i]
		if maxLen % 2 == 1:
			totaLen -= minLen * 2
		return totaLen


import heapq

class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		stks = 0
		mn = float('inf')
		for i in range(N):
			l = A[i]
			unit = B[i]
			if unit % 2 != 0:
				unit -= 1
			if unit >= 2:
				mn = min(l, mn)
			ans += l * unit
			stks += unit
		if stks % 4 != 0:
			ans -= 2 * mn
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		B = [i - i % 2 for i in B]
		j = 0
		tollen = 0
		tolcou = 0
		shortstick = 10 ** 5
		for m in range(N):
			if B[m] != 0:
				shortstick = min(shortstick, A[m])
				tolcou += B[m]
				tollen += A[m] * B[m]
		if tolcou % 4 != 0:
			tollen -= 2 * shortstick
		return tollen


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		rlen = 0
		rmin = smin = max(A)
		for i in range(N):
			temp = int(B[i] / 4)
			if temp:
				ans = ans + 4 * A[i] * temp
				if smin > A[i]:
					smin = A[i]
			temp = B[i] % 4
			if temp > 1:
				rlen = rlen + 1
				ans = ans + 2 * A[i]
				if rmin > A[i]:
					rmin = A[i]
		if rlen % 2 == 1:
			ans = ans - 2 * rmin
			if smin < rmin:
				ans = ans + 2 * (rmin - smin)
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		min_stick_len = A[0]
		sum_of_pair_lens = 0
		total_no_of_stick_pairs = 0
		for i in range(N):
			no_of_stick_pairs = B[i] // 2
			sum_of_pair_lens += no_of_stick_pairs * 2 * A[i]
			total_no_of_stick_pairs += no_of_stick_pairs
			if min_stick_len > A[i] and no_of_stick_pairs > 0:
				min_stick_len = A[i]
		if total_no_of_stick_pairs % 2 > 0:
			sum_of_pair_lens -= 2 * min_stick_len
		return sum_of_pair_lens


class Solution:

	def maxPossibleValue(self, N, A, B):
		total_len = 0
		min_len = float('inf')
		amount = 0
		for idx in range(len(A)):
			if B[idx] < 2:
				continue
			temp_amount = B[idx] // 2 * 2
			amount += temp_amount
			total_len += A[idx] * temp_amount
			if A[idx] < min_len:
				min_len = A[idx]
		if amount % 4 != 0:
			total_len -= 2 * min_len
		return total_len


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		c1 = 0
		mini = 9999999
		for i in range(0, N):
			if B[i] % 2 == 1:
				B[i] -= 1
			ans += A[i] * B[i]
			c1 += B[i] % 4
			if A[i] < mini and B[i] > 1:
				mini = A[i]
		if c1 % 4 != 0:
			ans -= mini * 2
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		cnt = 0
		mn = float('inf')
		for i in range(N):
			mod = B[i] % 4
			ans += A[i] * (B[i] - int(B[i] & 1))
			if mod == 0:
				cnt += 2
			elif mod > 1:
				cnt += 1
			if B[i] > 1:
				mn = min(A[i], mn)
		if cnt & 1:
			ans -= 2 * mn
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		mini = 10000000
		pv = 0
		for i in range(N):
			if B[i] > 1:
				used = B[i] // 4
				ans += used * A[i] * 4
				if B[i] != 1:
					mini = min(mini, A[i])
				if B[i] % 4 == 2 or B[i] % 4 == 3:
					if pv == 0:
						pv = A[i]
					else:
						ans += 2 * pv + 2 * A[i]
						pv = 0
		if pv != 0:
			return max(ans, ans - 2 * mini + 2 * pv)
		return ans


class Solution:

	def maxPossibleValue(self, N, a, b):
		ans = 0
		total_sticks = 0
		minimum_len = 10 ** 10
		for i in range(N):
			length = a[i]
			unit = b[i]
			if unit % 2 != 0:
				unit -= 1
			if unit >= 2:
				minimum_len = min(minimum_len, length)
			ans += length * unit
			total_sticks += unit
		if total_sticks % 4 != 0:
			ans -= 2 * minimum_len
		return ans


class Solution:

	def maxPossibleValue(self, n, a, b):
		s = 0
		y = -1
		z = -1
		s2 = 0
		m = 10000001
		ct = 0
		for i in range(n - 1, -1, -1):
			if b[i] >= 2:
				x = b[i] // 2
				x *= 2
				s += a[i] * x
				s2 += x
				if a[i] < m:
					m = a[i]
		y = s2 // 2
		if y % 2 != 0:
			s -= m * 2
		return s


class Solution:

	def maxPossibleValue(self, N, A, B):
		mini = 1000000000
		ts = 0
		tp = 0
		for i in range(N):
			if B[i] % 2 == 1:
				B[i] -= 1
			if B[i] >= 2:
				mini = min(mini, A[i])
			ts += B[i]
			tp += B[i] * A[i]
		if ts % 4 != 0:
			tp -= 2 * mini
		return tp


class Solution:

	def maxPossibleValue(self, N, A, B):
		m = float('inf')
		t = ans = 0
		for i in range(N):
			if B[i] >= 2:
				m = min(m, A[i])
				ans += A[i] * (B[i] - B[i] % 2)
				t += B[i] // 2 * 2
		return ans if t % 4 == 0 else ans - m * 2


class Solution:

	def maxPossibleValue(self, n, A, B):
		res = 0
		for i in range(n):
			if B[i] & 1:
				B[i] -= 1
		minm = 1000000.0
		count = 0
		for i in range(n):
			count += B[i]
			res += A[i] * B[i]
			if B[i] != 0:
				minm = min(minm, A[i])
		if count % 4 == 2:
			res -= minm * 2
		return res


class Solution:

	def maxPossibleValue(self, N, a, b):
		count = 0
		ans = 0
		mn = 99999999999999
		for i in range(N):
			if b[i] > 1:
				ans += a[i] * (b[i] - b[i] % 2)
				mn = min(mn, a[i])
				count += b[i] - b[i] % 2
		if count % 4 != 0:
			ans -= 2 * mn
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		count = 0
		min_A = float('inf')
		total_sum = 0
		for i in range(N):
			n = B[i] // 2
			if n > 0:
				total_sum += A[i] * n * 2
				count += n
				if A[i] < min_A:
					min_A = A[i]
		if count % 2 != 0:
			total_sum -= min_A * 2
		return total_sum


class Solution:

	def maxPossibleValue(self, N, A, B):
		s = 0
		l = 0
		m = 1000000000.0
		for i in range(N):
			if B[i] >= 2:
				m = min(m, A[i])
				l += A[i] * (B[i] // 2) * 2
				s += B[i] // 2 * 2
		s = s % 4
		l -= s * m
		return int(l)


class Solution:

	def maxPossibleValue(self, N, A, B):
		count = 0
		ans = 0
		ss = 10 ** 9
		for i in range(N):
			if B[i] // 2 > 0:
				count = count + B[i] // 2
				ans = ans + A[i] * (B[i] // 2) * 2
				ss = min(ss, A[i])
		if count % 2 == 1:
			ans = ans - ss * 2
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		mn = int(1000000000.0)
		count = 0
		res = 0
		for i in range(N):
			if B[i] > 1:
				rect_pairs = B[i] // 2
				res += 2 * (rect_pairs * A[i])
				mn = min(mn, A[i])
				count += rect_pairs
		if count % 2 != 0:
			res -= 2 * mn
		return res


import sys

class Solution:

	def maxPossibleValue(self, N, A, B):
		min_ = sys.maxsize
		ans = 0
		count = 0
		for i in range(N):
			if A[i] < min_ and B[i] > 1:
				min_ = A[i]
			d = B[i] // 2
			ans += d * 2 * A[i]
			count += d * 2
		if count % 4 != 0:
			ans -= min_ * 2
		return ans


import math

class Solution:

	def maxPossibleValue(self, N, A, B):
		(ans, min_side, ct) = (0, math.inf, 0)
		for i in range(N):
			ans += A[i] * (B[i] // 4) * 4
			remaining = B[i] % 4
			if B[i] > 1:
				min_side = min(min_side, A[i])
			if remaining > 1:
				ans += A[i] * 2
				ct += 1
		if ct % 2 == 1:
			ans -= min_side * 2
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		d = {}
		a = set()
		for i in range(N):
			d[A[i]] = B[i]
			a.add(A[i])
		A = sorted(list(a), reverse=True)
		s = 0
		stock = 0
		for n in A:
			if stock > 0:
				if d[n] >= 2:
					s += stock + 2 * n
					d[n] -= 2
					stock = 0
			if d[n] >= 4:
				t = d[n] // 4
				s += t * n * 4
				d[n] %= 4
			if d[n] >= 2:
				stock = 2 * n
		return s


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		t = 0
		z = 0
		for i in range(N):
			B[i] //= 2
		x = float('inf')
		for i in range(N):
			if B[i]:
				x = min(A[i], x)
			t += B[i] * A[i]
			z += B[i]
		if z % 2 == 1:
			t -= x
		return t * 2


class Solution:

	def maxPossibleValue(self, N, A, B):
		import math
		sum = 0
		total = 0
		minimum = math.inf
		for i in range(len(A)):
			ini = A[i]
			big = B[i]
			if big % 2:
				big = big - 1
			if big >= 2:
				minimum = min(minimum, ini)
			sum = sum + big * ini
			total = total + big
		if total % 4 != 0:
			sum = sum - (minimum + minimum)
		return sum


class Solution:

	def maxPossibleValue(self, N, A, B):
		c = 0
		res = 0
		minn = 10 ** 6
		for i in range(N):
			if B[i] >= 2:
				res += 2 * A[i] * (B[i] // 2)
				c += B[i] // 2
				minn = min(minn, A[i])
		if c & 1:
			res -= 2 * minn
		return res


class Solution:

	def maxPossibleValue(self, N, A, B):
		frequencies = {A[index]: B[index] for index in range(N) if B[index] > 1}
		sticks = sorted(frequencies, reverse=True)
		summation = lastPart = 0
		for stick in sticks:
			if lastPart:
				if frequencies[stick] > 1:
					summation += lastPart + 2 * stick
					frequencies[stick] -= 2
					lastPart = 0
			summation += frequencies[stick] // 4 * stick * 4
			frequencies[stick] %= 4
			if frequencies[stick] > 1:
				lastPart += stick * 2
		return summation


class Solution:

	def maxPossibleValue(self, N, A, B):
		mn = float('inf')
		count = 0
		res = 0
		for i in range(N):
			if B[i] > 1:
				rect_pairs = B[i] // 2
				res += 2 * (rect_pairs * A[i])
				mn = min(mn, A[i])
				count += rect_pairs
		if count % 2 != 0:
			res -= 2 * mn
		return res


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		count = 0
		m = 10 ** 6
		for i in range(N):
			if B[i] > 1:
				count += B[i] // 2
				ans += A[i] * (B[i] // 2) * 2
				m = min(m, A[i])
		if count & 1:
			ans -= 2 * m
		return ans


class Solution:

	def maxPossibleValue(self, N, A, B):
		ans = 0
		minn = float('inf')
		total_sticks_used = 0
		for i in range(0, N):
			temp = B[i] // 2
			ans += A[i] * temp * 2
			total_sticks_used += temp * 2
			if temp >= 1:
				minn = min(minn, A[i])
		if total_sticks_used % 4 == 0:
			return ans
		return ans - minn * 2


class Solution:

	def maxPossibleValue(self, N, A, B):
		out = 0
		rec = float('inf')
		count = 0
		for i in range(N):
			if B[i] >= 4:
				out += B[i] // 4 * A[i] * 4
				B[i] = B[i] % 4
				rec = min(rec, A[i])
			if B[i] >= 2:
				out += B[i] // 2 * A[i] * 2
				B[i] = B[i] % 2
				count += 1
				rec = min(rec, A[i])
		return out if count % 2 == 0 else out - 2 * rec


from math import inf

class Solution:

	def maxPossibleValue(self, N, A, B):
		sticks_count = 0
		max_sum = 0
		min_len = 10 ** 5 + 1
		for i in range(N):
			if B[i] > 1:
				if B[i] % 2 != 0:
					B[i] = B[i] - 1
				sticks_count = sticks_count + B[i]
				max_sum = max_sum + A[i] * B[i]
				if min_len > A[i]:
					min_len = A[i]
		if sticks_count % 4:
			max_sum = max_sum - 2 * min_len
		return max_sum


import sys

class Solution:

	def maxPossibleValue(self, N, A, B):
		total_sum = 0
		total_sticks = 0
		min_length_stick = sys.maxsize
		for i in range(N):
			len = A[i]
			units = B[i]
			if units % 2 != 0:
				units -= 1
			if units >= 2:
				min_length_stick = min(len, min_length_stick)
			total_sum += len * units
			total_sticks += units
		if total_sticks % 4 != 0:
			total_sum -= min_length_stick * (total_sticks % 4)
		return total_sum


class Solution:

	def maxPossibleValue(self, n, a, b):
		ans = 0
		c = 0
		max = a[0]
		d = b[0]
		for i in range(n):
			if a[i] < max and b[i] >= 2:
				max = a[i]
			c = c + b[i] // 2
			ans += a[i] * 2 * (b[i] // 2)
		if c % 2 == 0:
			return ans
		else:
			ans -= 2 * max
			return ans