Прошло много лет, и на вечеринке снова встретились 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: interview

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)
##    m1 = ((cw+a)*max(ch, b))
##    m2 = ((cw+b)*max(ch, a))
##    if m1 < m2:
##        cw += a
##        ch = max(ch, b)
##    else:
##        cw += b
##        ch = max(ch, a)
##
##print(cw*ch)


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]
        else:
            if (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)
        





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

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 = 1e10
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 )


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)




# Made By Mostafa_Khaled


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
            else:
                if j[0] <= i and j[1] <= i:
                    curr+=min(j[0], j[1])
                else:
                    curr+=max(j[0], j[1])
        if f:
            #print(i,curr)
            ans=min(ans, curr*i)
    print(ans)

    return


def __starting_point():
    main()
__starting_point()