Прошло много лет, и на вечеринке снова встретились n друзей. С момента последней встречи техника шагнула далеко вперёд, появились фотоаппараты с автоспуском, и теперь не требуется, чтобы один из друзей стоял с фотоаппаратом, и, тем самым, оказывался не запечатлённым на снимке.

Упрощенно процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: в стоячем положении i-й из них занимает прямоугольник ширины w_{i} пикселей и высоты h_{i} пикселей. Но также, при фотографировании каждый человек может лечь, и тогда он будет занимать прямоугольник ширины h_{i} пикселей и высоты w_{i} пикселей.

Общая фотография будет иметь размеры W × H, где W — суммарная ширина всех прямоугольников-людей, а H — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография. Помогите им в этом.


-----Входные данные-----

В первой строке следует целое число n (1 ≤ n ≤ 1000) — количество друзей.

В последующих n строках следуют по два целых числа w_{i}, h_{i} (1 ≤ w_{i}, h_{i} ≤ 1000), обозначающие размеры прямоугольника, соответствующего i-му из друзей.


-----Выходные данные-----

Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.


-----Примеры-----
Входные данные
3
10 1
20 2
30 3

Выходные данные
180

Входные данные
3
3 1
2 2
4 3

Выходные данные
21

Входные данные
1
5 10

Выходные данные
50

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def main():
	import sys
	tokens = [int(i) for i in sys.stdin.read().split()]
	tokens.reverse()
	n = tokens.pop()
	people = [(tokens.pop(), tokens.pop()) for i in range(n)]
	result = float('inf')
	for i in range(n):
		for j in range(2):
			maxh = people[i][j]
			S = people[i][j ^ 1]
			for k in range(n):
				if k != i:
					(w, h) = people[k]
					(w, h) = (min(w, h), max(w, h))
					if w > maxh:
						S = float('inf')
						break
					if h > maxh:
						S += h
					else:
						S += w
			result = min(result, S * maxh)
	print(result)
main()


t = []
x = int(input())
for i in range(x):
	(a, b) = list(map(int, input().split(' ')))
	lx = [a, b]
	lx.sort()
	t.append(lx)
t.sort()
minn = 10 ** 9
for i in range(x):
	h = t[i][0]
	w = t[i][1]
	ok = 1
	for j in range(x):
		if ok == 1 and j != i:
			if min(t[j]) > h:
				ok = 0
			elif min(t[j]) <= h < max(t[j]):
				w += max(t[j])
			else:
				w += min(t[j])
	if ok == 1:
		minn = min(minn, w * h)
for i in t:
	i.reverse()
for i in range(x):
	h = t[i][0]
	w = t[i][1]
	ok = 1
	for j in range(x):
		if ok == 1 and j != i:
			if min(t[j]) > h:
				ok = 0
			elif min(t[j]) <= h < max(t[j]):
				w += max(t[j])
			else:
				w += min(t[j])
	if ok == 1:
		minn = min(minn, w * h)
print(minn)


a = []
heights = []
wid = 0
hei = 0
heim = 1000
n = int(input())
for i in range(n):
	(w, h) = list(map(int, input().split()))
	if w > h:
		x = w
		w = h
		h = x
	wid += w
	if hei < h:
		hei = h
	if heim > w:
		heim = w
	a.append((h, w))
last = wid * hei
for i in range(heim, hei + 1):
	wid1 = 0
	hei1 = i
	for j in range(0, n):
		if a[j][0] <= i:
			wid1 += a[j][1]
		elif a[j][1] <= i:
			wid1 += a[j][0]
		else:
			wid1 += 1000000000
			break
	if wid1 * i < last:
		last = wid1 * i
print(last)


n = int(input().rstrip())
d = []
for i in range(n):
	(w, h) = list(map(int, input().rstrip().split()))
	d.append([w, h])
s = '.'
for i in range(len(d)):
	h = d[i][0]
	w = d[i][1]
	f = 1
	for j in range(len(d)):
		if j != i:
			if d[j][0] <= h and d[j][1] <= h:
				w += min(d[j][0], d[j][1])
			elif d[j][0] <= h and d[j][1] > h:
				w += d[j][1]
			elif d[j][0] > h and d[j][1] <= h:
				w += d[j][0]
			else:
				f = 0
	if not f == 0:
		if s == '.' or h * w < s:
			s = h * w
	h = d[i][1]
	w = d[i][0]
	f = 1
	for j in range(len(d)):
		if j != i:
			if d[j][0] <= h and d[j][1] <= h:
				w += min(d[j][0], d[j][1])
			elif d[j][0] <= h and d[j][1] > h:
				w += d[j][1]
			elif d[j][0] > h and d[j][1] <= h:
				w += d[j][0]
			else:
				f = 0
	if not f == 0:
		if s == '.' or h * w < s:
			s = h * w
print(s)


n = int(input())
data = []
for j in range(n):
	data.append([int(i) for i in input().split()])
s = 1000 * 1000 * 1000 + 1
for h in range(1, 1001):
	w = 0
	ok = True
	for i in data:
		h1 = max(i[0], i[1])
		w1 = min(i[0], i[1])
		if w1 > h:
			ok = False
			break
		if h1 > h:
			w += h1
		else:
			w += w1
	if ok:
		s = min(s, h * w)
print(s)


n = int(input())
ar = []
for i in range(n):
	(a, b) = map(int, input().split())
	ar.append((a, b))
l = 0
hmin = 0
for i in ar:
	hmin = max(hmin, min(i[0], i[1]))
s = 10000000000000
for h in range(hmin, 1001):
	l = 0
	for i in ar:
		if i[0] > h:
			l += i[0]
		elif i[1] > h:
			l += i[1]
		else:
			l += min(i[0], i[1])
	s = min(s, l * h)
print(s)


n = int(input())
inf = 10 ** 9 + 11
arr = []
for i in range(n):
	wh = list(map(int, input().split()))
	wh.sort()
	arr.append(wh)
best_S = inf
cur_S = 0
for h in range(1, 1001):
	cur_S = 0
	for j in range(n):
		if arr[j][0] > h:
			cur_S = inf
			break
		if arr[j][1] <= h:
			cur_S += arr[j][0]
		else:
			cur_S += arr[j][1]
	best_S = min(best_S, cur_S * h)
print(best_S)


n = int(input())
hs = []
ws = []
for i in range(n):
	(w, h) = list(map(int, input().split()))
	hs.append(h)
	ws.append(w)
ans = float('inf')
for H in range(1, 1001):
	wr = 0
	pos = True
	for j in range(n):
		a = min(hs[j], ws[j])
		b = max(hs[j], ws[j])
		if b <= H:
			wr += a
		elif a <= H:
			wr += b
		else:
			pos = False
			break
	if not pos:
		continue
	r = H * wr
	if r < ans:
		ans = r
print(ans)


N = int(input())
W = [0 for i in range(N)]
H = [0 for i in range(N)]
for i in range(N):
	(W[i], H[i]) = list(map(int, input().split()))
	if not W[i] <= H[i]:
		(W[i], H[i]) = (H[i], W[i])
maxw = max(W)
ans = 10000000000.0
while maxw <= 1000:
	s = 0
	for i in range(N):
		if maxw >= H[i]:
			s += W[i]
		else:
			s += H[i]
	if ans > maxw * s:
		ans = maxw * s
	maxw += 1
print(ans)


import math
R = lambda : map(int, input().split())
n = int(input())
arr = []
for i in range(n):
	(h, w) = R()
	arr.append([h, w])
dp = [[math.inf] * 1001 for i in range(n)] + [[0] * 1001]
for i in range(n):
	for j in range(1001):
		if j >= max(arr[i]):
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + j * min(arr[i]))
		elif j >= min(arr[i]):
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + j * max(arr[i]))
print(min(dp[n - 1]))


mem = int(input())
array = []
for i in range(mem):
	str = input()
	array.append([int(x) for x in str.split()])
max_height = 0
weight = 0
for i in array:
	max_height = max(min(i[0], i[1]), max_height)
pl = 10000000000000
for h in range(max_height, 1001):
	weight = 0
	for i in array:
		if i[0] > h:
			weight += i[0]
		elif i[1] > h:
			weight += i[1]
		else:
			weight += min(i[0], i[1])
	pl = min(pl, weight * h)
print(pl)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

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

def main():
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	ans = float('inf')
	for i in range(1, 1001):
		f = 1
		curr = 0
		for j in a:
			if j[0] > i and j[1] > i:
				f = 0
				break
			elif j[0] <= i and j[1] <= i:
				curr += min(j[0], j[1])
			else:
				curr += max(j[0], j[1])
		if f:
			ans = min(ans, curr * i)
	print(ans)
	return

def __starting_point():
	main()
__starting_point()