Little C loves number «3» very much. He loves all things about it.

Now he is playing a game on a chessboard of size $n \times m$. The cell in the $x$-th row and in the $y$-th column is called $(x,y)$. Initially, The chessboard is empty. Each time, he places two chessmen on two different empty cells, the Manhattan distance between which is exactly $3$. The Manhattan distance between two cells $(x_i,y_i)$ and $(x_j,y_j)$ is defined as $|x_i-x_j|+|y_i-y_j|$.

He want to place as many chessmen as possible on the chessboard. Please help him find the maximum number of chessmen he can place.


-----Input-----

A single line contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^9$) — the number of rows and the number of columns of the chessboard.


-----Output-----

Print one integer — the maximum number of chessmen Little C can place.


-----Examples-----
Input
2 2

Output
0
Input
3 3

Output
8


-----Note-----

In the first example, the Manhattan distance between any two cells is smaller than $3$, so the answer is $0$.

In the second example, a possible solution is $(1,1)(3,2)$, $(1,2)(3,3)$, $(2,1)(1,3)$, $(3,1)(2,3)$.

Difficulty: HARD
Tags: Complete search

Flows and cuts

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
(n, m) = map(int, input().split())
q = min(n, m)
w = max(n, m)
if q == 1 and w <= 3 or q == 2 == w:
	print('0')
elif q == 1 and w == 4:
	print('2')
elif q == 1 and w == 5:
	print('4')
elif q == 1 and w == 6:
	print('6')
elif q == 2 and w == 3:
	print('4')
elif q == 1:
	r = w // 6
	if w % 6 == 0:
		print(w)
	elif w % 6 <= 3:
		print(r * 6)
	elif w % 6 == 4:
		print(r * 6 + 2)
	elif w % 6 == 5:
		print(r * 6 + 4)
elif q == 2 and w == 7:
	print('12')
elif q * w % 2 == 0:
	print(q * w)
else:
	print(q * w - 1)


(n, m) = [int(x) for x in input().split()]

def cal(n, m):
	if n < m:
		(n, m) = (m, n)
	if m == 1:
		dt = {0: 0, 1: 1, 2: 2, 3: 3, 4: 2, 5: 1}
		return dt[n % 6]
	if n == 7:
		if m == 2:
			return 2
		return n * m % 2
	elif n >= 4:
		return n * m % 2
	else:
		dt = {(3, 2): 2, (3, 1): 3, (2, 2): 4, (2, 1): 2}
		return dt.get((n, m), n * m % 2)
print(n * m - cal(n, m))


(n, m) = map(int, input().split())
if n > m:
	(n, m) = (m, n)
if n == 1:
	print(m // 6 + (m + 1) // 6 + (m + 2) // 6 << 1)
elif n == 2:
	print(0 if m == 2 else 4 if m == 3 else 12 if m == 7 else n * m)
else:
	print(n * m >> 1 << 1)


M = list(map(int, input().split()))
M.sort()
if M[0] == 1:
	(x, y) = divmod(M[1], 6)
	ANS = x * 6
	if y <= 3:
		print(ANS)
	elif y == 4:
		print(ANS + 2)
	elif y == 5:
		print(ANS + 4)
elif M[0] == 2:
	if M[1] == 2:
		print(0)
	elif M[1] == 3:
		print(4)
	elif M[1] == 7:
		print(12)
	else:
		print(M[1] * 2)
elif M[0] == 3:
	if M[1] == 3:
		print(8)
	elif M[1] >= 4:
		print(M[0] * M[1] // 2 * 2)
else:
	print(M[0] * M[1] // 2 * 2)


class Solution(object):

	def run(self):
		(n, m) = [int(x) for x in input().split()]
		if n > m:
			(n, m) = (m, n)
		res = n * m // 2
		if n == 1 and (m + 1) % 6 // 3:
			res -= 1
		elif n == 2:
			if m == 2:
				res = 0
			elif m == 3:
				res = 2
			elif m == 7:
				res = 6
		print(res * 2)
Solution().run()


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
(x, y) = map(int, input().split())
if x == 1:
	s = y % 6
	if s == 4:
		s = 2
	if s == 5:
		s = 1
	print(y - s)
	exit(0)
if y == 1:
	s = x % 6
	if s == 4:
		s = 2
	if s == 5:
		s = 1
	print(x - s)
	exit(0)
x1 = min(x, y)
y1 = max(x, y)
if x1 == 2:
	if y1 == 2:
		print(0)
	elif y1 == 3:
		print(4)
	elif y1 == 7:
		print(12)
	else:
		print(2 * y1)
else:
	print(x1 * y1 - x1 * y1 % 2)


(n, m) = map(int, input().split())
(m, n) = (max(m, n), min(n, m))
a = m * n
if m == 7 and n == 2:
	print(12)
	exit()
if m == 3 and n == 2:
	print(4)
	exit()
if n == 1:
	print(a - min(m % 6, 6 - m % 6))
elif m * n >= 6:
	print(n * m - n * m % 2)
else:
	print(0)


(n, m) = sorted(map(int, input().split()))
print(n * m - {1: min(m % 6, 6 - m % 6), 2: {2: 4, 3: 2, 7: 2}.get(m, 0)}.get(n, n & 1 * m & 1))


(n, m) = sorted(map(int, input().split()))
print(~1 & n * m - 2 * {1: 1 < m % 6 < 5, 2: {2: 2, 3: 1, 7: 1}.get(m, 0)}.get(n, 0))


(n, m) = map(int, input().split(' '))
if m > n:
	(n, m) = (m, n)
rowsGroups = n // 6
restRows = n % 6
count = 3 * rowsGroups * m
colsGroups = m // 6
restCols = m % 6
count += 3 * colsGroups * restRows
if not (restRows == 0 or restCols == 0):
	(sn, sm) = (restRows, restCols)
	if sm > sn:
		(sn, sm) = (sm, sn)
	if (sn, sm) == (1, 1):
		count += 0
	elif (sn, sm) == (5, 1):
		count += 2
	elif (sn, sm) == (4, 2):
		count += 4
	elif (sn, sm) == (5, 2):
		count += 5
	elif (sn, sm) == (3, 3):
		count += 4
	elif (sn, sm) == (4, 3):
		count += 6
	elif (sn, sm) == (5, 3):
		count += 7
	elif (sn, sm) == (4, 4):
		count += 8
	elif (sn, sm) == (5, 4):
		count += 10
	elif (sn, sm) == (5, 5):
		count += 12
	elif (sn, sm) == (2, 1):
		if restRows == 2:
			if colsGroups >= 2 or (colsGroups == 1 and rowsGroups >= 1):
				count += 1
		elif restCols == 2:
			if rowsGroups >= 2 or (rowsGroups == 1 and colsGroups >= 1):
				count += 1
	elif (sn, sm) == (3, 1):
		if restRows == 3 and colsGroups >= 1:
			count += 1
		if restCols == 3 and rowsGroups >= 1:
			count += 1
	elif (sn, sm) == (4, 1):
		if restRows == 4 and colsGroups >= 1:
			count += 2
		elif restCols == 4 and rowsGroups >= 1:
			count += 2
		else:
			count += 1
	elif (sn, sm) == (2, 2):
		if rowsGroups >= 1 or colsGroups >= 1:
			count += 2
	elif (sn, sm) == (3, 2):
		if rowsGroups >= 1 or colsGroups >= 1:
			count += 3
		else:
			count += 2
	else:
		raise f'Unknown pair ({(sn, sm)})'
print(2 * count)


(n, m) = map(int, input().strip().split())
f = min(n, m)
f1 = max(n, m)

def s(g):
	if g % 6 == 1 or g % 6 == 5:
		return 1
	if g % 6 == 2 or g % 6 == 4:
		return 2
	if g % 6 == 0:
		return 0
	if g % 6 == 3:
		return 3
if f == 1:
	f3 = s(f1)
	print(n * m - f3)
	exit(0)
if f == 2 and f1 == 3:
	print(4)
	exit(0)
if f == 2 and f1 == 2:
	print(0)
	exit(0)
if f == 2 and f1 == 7:
	print(12)
	exit(0)
if f == 3 and f1 == 3:
	print(8)
	exit(0)
if f % 2 == 0 and f1 % 2 == 0:
	print(n * m)
	exit(0)
if f % 2 == 1 and f1 % 2 == 0:
	print(n * m)
	exit(0)
if f % 2 == 0 and f1 % 2 == 1:
	print(n * m)
	exit(0)
if f % 2 == 1 and f1 % 2 == 1:
	print(n * m - 1)
	exit(0)


(n, m) = [int(i) for i in input().split()]
(m, n) = (max(m, n), min(n, m))
a = m * n
if m == 7 and n == 2:
	print(12)
	exit()
if m == 3 and n == 2:
	print(4)
	exit()
if n == 1:
	print(a - min(m % 6, 6 - m % 6))
elif m * n >= 6:
	print(n * m - n * m % 2)
else:
	print(0)


(n, m) = map(int, input().split())
if n > m:
	(n, m) = (m, n)
if n == 1:
	print(m // 6 * 6 + max(m % 6 * 2 - 6, 0))
elif n == 2:
	if m == 2:
		print(0)
	elif m == 3 or m == 7:
		print(m * 2 - 2)
	else:
		print(m * 2)
else:
	print(n * m // 2 * 2)


(n, m) = map(int, input().split())
if n * m < 4 and (n == 1 or m == 1) or (n * m < 5 and (n != 1 and m != 1)):
	print(0)
else:
	l = n * m
	if n % 2 == 0 and m % 2 == 0:
		if n == m:
			if n % 3 != 0 and n % 4 != 0:
				print(l - 4)
			else:
				print(l)
		elif n % 4 == 0 or m % 4 == 0:
			print(l)
		elif n % 3 == 0 or m % 3 == 0:
			print(l)
		else:
			print(l - 2)
	elif n % 2 != 0 and m % 2 != 0:
		if n == 1 or m == 1:
			z = max(n, m)
			if z % 6 == 0:
				print(z)
			else:
				s1 = z // 6 * 6
				r = z % 6
				if r > 3:
					s1 = s1 + 2
					r = r % 4
					s1 = s1 + r * 2
				print(s1)
		else:
			print(l - 1)
	elif n == 1 or m == 1:
		z = max(n, m)
		if z % 6 == 0:
			print(z)
		else:
			s1 = z // 6 * 6
			r = z % 6
			if r > 3:
				s1 = s1 + 2
				r = r % 4
				s1 = s1 + r * 2
			print(s1)
	elif n % 4 == 0 or m % 4 == 0:
		print(l)
	elif n % 6 == 0 or m % 6 == 0:
		print(l)
	else:
		if n % 2 == 0:
			z = m
		else:
			z = n
		if z % 4 == 1:
			print(l)
		elif z >= 6:
			if z % 6 == 1:
				if z > 7 and z % 4 == 3:
					print(l)
				else:
					print(l - 2)
			elif z % 6 == 5 and z % 4 == 3:
				print(l)
			elif z % 6 == 3:
				print(l)
		else:
			print(l - 2)


(n, m) = map(int, input().split())
if n < m:
	(n, m) = (m, n)
ans = 0
d = {0: 0, 1: 1, 2: 2, 3: 3, 4: 2, 5: 1}
if m == 1:
	ans = d[n % 6]
elif m == 2:
	if n == 3:
		ans = 2
	elif n == 2:
		ans = 4
	elif n == 7:
		ans = 2
else:
	ans = n * m % 2
print(n * m - ans)


(n, m) = map(int, input().split())
if n > m:
	(n, m) = (m, n)
print(n * m - (min(m % 6, 6 - m % 6) if n == 1 else 2 * (m in [3, 7]) + 4 * (m == 2) if n == 2 else n & 1 * m & 1))


import math
from decimal import *
getcontext().prec = 30
(n, m) = map(int, input().split())
ans = 0
if n < m:
	(n, m) = (m, n)
if n < 3 and m < 3:
	ans = 0
elif m == 1:
	ans += n // 6 * 6
	n %= 6
	if n > 3:
		ans += (n - 3) * 2
elif n % 4 == 0 or m % 4 == 0 or n % 6 == 0 or (m % 6 == 0):
	ans = n * m
elif n <= 5 and m <= 5:
	if n % 2 and m % 2:
		ans = n * m - 1
	elif n == 3:
		ans = n * m - 2
	else:
		ans = n * m
elif n * m == 14:
	ans = 12
else:
	ans = n * m // 2 * 2
print(ans)


(n, m) = map(int, input().split())
a = n * m
if n > m:
	(n, m) = (m, n)
if n == 1:
	a -= min(m % 6, 6 - m % 6)
elif n == 2:
	a -= 2 * (abs(5 - m) == 2) + 4 * (m == 2)
else:
	a -= n & 1 * m & 1
print(a)


(n, m) = map(int, input().split())
(min_, max_) = (min(n, m), max(n, m))
arr1 = [1, 2, 3, 2, 1, 0]
arr2 = [2, 4, 2, 0, 0, 0, 2]
if min_ == 1:
	r = arr1[(max_ - 1) % 6]
elif min_ == 2:
	if max_ <= 7:
		r = arr2[max_ - 1]
	else:
		r = 0
else:
	r = n * m % 2
print(n * m - r)


def main():
	(n, m) = map(int, input().split())
	if m > n:
		(n, m) = (m, n)
	if n + m <= 4:
		print(0)
		return
	if m == 1:
		q = n // 6
		r = n % 6
		if r == 4:
			print(n - 2)
		elif r == 5:
			print(n - 1)
		else:
			print(q * 6)
		return
	if (n, m) in [(7, 2), (3, 2)]:
		print(n * m - 2)
		return
	if n % 2 == 0 or m % 2 == 0:
		print(n * m)
		return
	print(n * m - 1)
main()


(a, b) = map(int, input().split())
(a, b) = (min(a, b), max(a, b))
if a == 1:
	c = b % 6
	if c == 4:
		print(b // 6 * 6 + 2)
	elif c == 5:
		print(b // 6 * 6 + 4)
	else:
		print(b // 6 * 6)
elif a == 2:
	if b <= 2:
		print(0)
	elif b == 3 or b == 7:
		print(a * b - 2)
	else:
		print(b * 2)
else:
	ans = a * b
	if ans % 2 == 0:
		print(ans)
	else:
		print(ans - 1)


[n, m] = list(map(int, input().split()))
solutions = 0
if m < n:
	temp = m
	m = n
	n = temp
if n >= 3:
	if n % 2 == 1 and m % 2 == 1:
		solutions = n * m - 1
	else:
		solutions = n * m
if n == 1:
	if m <= 3:
		solutions = 0
	if m % 6 == 0:
		solutions = m
	if m % 6 == 1 or m % 6 == 5:
		solutions = m - 1
	if m % 6 == 2 or m % 6 == 4:
		solutions = m - 2
	if m % 6 == 3:
		solutions = m - 3
if n == 2:
	if m <= 2:
		solutions = 0
	elif m <= 3:
		solutions = m * n - 2
	elif m <= 6:
		solutions = m * n
	elif m <= 7:
		solutions = m * n - 2
	else:
		solutions = m * n
print(solutions)


(n, m) = map(int, input().split())
if n >= 4 and m >= 4:
	print(n * m - n * m % 2)
elif min(n, m) == 1:
	if max(n, m) % 6 == 5:
		print(max(n, m) // 6 * 6 + 4)
	elif max(n, m) % 6 == 4:
		print(max(n, m) // 6 * 6 + 2)
	else:
		print(max(n, m) // 6 * 6)
elif min(n, m) == 2 and max(n, m) == 7:
	print(12)
elif min(n, m) == 2 and max(n, m) >= 4 or (min(n, m) == 3 and max(n, m) >= 4):
	print(n * m - n * m % 2)
else:
	d = [[0, 0, 0, 2, 4], [0, 0, 4, 8, 10], [0, 0, 8, 12, 14], [0, 0, 0, 16, 20], [0, 0, 0, 0, 24]]
	print(d[min(n, m) - 1][max(n, m) - 1])


(N, M) = map(int, input().split())
l = [0, 1, 2, 3, 2, 1]
res = float('inf')
for (n, m) in ((N, M), (M, N)):
	if l[n % 6] == 0:
		print(n * m)
		exit()
	elif l[n % 6] == 1:
		tmp = l[m % 6]
		res = min(res, tmp)
	elif l[n % 6] == 2:
		if m >= 4 and m != 7:
			print(n * m)
			exit()
		if m == 2:
			tmp = 4
		else:
			tmp = 2
		res = min(res, tmp)
	else:
		if m == 1:
			tmp = 3
		elif m == 2:
			tmp = 2
		elif m % 2 == 0:
			print(n * m)
			exit()
		else:
			tmp = 1
		res = min(res, tmp)
print(n * m - res)


import math
import sys
(n, m) = list(map(int, input().split()))
if n > m:
	(n, m) = (m, n)
if n == 1:
	print(6 * (m // 6) + 2 * max(0, m % 6 - 3))
elif n == 2:
	if m == 2:
		print(0)
	elif m in (1, 3, 7):
		print(n * m - 2)
	else:
		print(n * m)
else:
	print(n * m // 2 * 2)


known = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 2, 4], [0, 0, 0, 4, 8, 10], [0, 0, 4, 8, 12, 14], [0, 2, 8, 12, 16, 20], [0, 4, 10, 14, 20, 24]]
(n, m) = map(int, input().split(' '))
if n > m:
	(n, m) = (m, n)
if n <= 5 and m <= 5:
	print(known[m][n])
elif n == 1:
	print(6 * (m // 6) + [0, 0, 0, 0, 2, 4][m % 6])
elif n == 2:
	if m == 7:
		print(12)
	else:
		print(2 * m)
else:
	print(2 * int(m * n // 2))