Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from itertools import combinations
n,k = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(n)]
ans = 1e100
for l,r in combinations(range(n),2):
  for b,t in combinations(range(n),2):
    left,right = sorted([XY[l][0], XY[r][0]])
    bottom,top = sorted([XY[b][1], XY[t][1]])
    cnt = 0
    for x,y in XY:
      if left <= x <= right and bottom <= y <= top:
        cnt += 1
    if cnt >= k:
      ans = min(ans, (top - bottom)*(right - left))
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
X = [0]*n
Y = [0]*n
for i in range(n):
    X[i],Y[i] = map(int,input().split())

Xs = sorted(X)
Ys = sorted(Y)
XY = sorted(list(zip(X,Y)))
ans = 1e100
for i in range(n-k+1):
    for j in range(i+k-1,n):
        w = Xs[j] - Xs[i]
        XYs = sorted(XY[i:j+1],key = lambda x:x[1])
        h = 1e100
        for l in range(len(XYs) - k + 1):
            h = min(h, XYs[l + k - 1][1] - XYs[l][1])
        ans = min(ans , h*w)
print(ans)
### BUGGY CODE ###



n = int(input())
l = list(map(int, input().split()))

ans = 1
for i in range(n):
    ans *= l[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from sys import stdin
input = stdin.readline



n = int(input())
l = list(map(int, input().split()))

ans = 1
ng = False
for i in range(n):
    if l[i] == 0:
        print(0)
        quit()
    if not ng:
        ans *= l[i]
        if ans > 10**18:
            ng = True

if ng:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = getlist()
	ans = 0
	for i in range(29):
		mul = 2 ** (i + 1)
		mul2 = 2 ** i
		Aex = [A[j] % mul for j in range(N)]
		Bex = [B[j] % mul for j in range(N)]
		Bex.sort()
		cnt = 0
		for j in range(N):
			var = Aex[j]
			if var <= 2 ** i:
				cnt += bisect.bisect_left(Bex, mul - var) - (bisect.bisect_left(Bex, mul2 - var))
			else:
				cnt += bisect.bisect_left(Bex, mul - var)
				cnt += N - bisect.bisect_left(Bex, mul + mul2 - var)
		# print(Aex)
		# print(Bex)
		# print(cnt)
		if cnt % 2 != 0:
			ans += 2 ** i

	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = getlist()
	ans = 0
	for i in range(29):
		mul = 2 ** (i + 1)
		mul2 = 2 ** i
		Aex = [A[j] % mul for j in range(N)]
		Bex = [B[j] % mul for j in range(N)]
		Aex.sort()
		Bex.sort()
		cnt = 0
		p, q, r = N - 1, N - 1, N - 1
		for j in range(N):
			var = Aex[j]
			while p >= 0 and mul2 - var <= Bex[p]:
				p -= 1
			while q >= 0 and mul - var <= Bex[q]:
				q -= 1
			while r != 0 and mul + mul2 - var <= Bex[r]:
				r -= 1
			cnt += q - p
			cnt += N - 1 - r
			
			# if var <= 2 ** i:
			# 	cnt += bisect.bisect_left(Bex, mul - var) - (bisect.bisect_left(Bex, mul2 - var))
			# else:
			# 	cnt += bisect.bisect_left(Bex, mul - var)
			# 	cnt += N - bisect.bisect_left(Bex, mul + mul2 - var)
		# print(Aex)
		# print(Bex)
		# print(cnt)
		if cnt % 2 != 0:
			ans += 2 ** i

	print(ans)

if __name__ == '__main__':
	main()
### BUGGY CODE ###

import numpy as np
n,A=tuple(map(lambda x:int(x),input().split()))
x=tuple(map(lambda x:int(x),input().split()))
dp=np.zeros((n+1,n+1,n*A+1), dtype=int)
dp[0,0,0]=1
for i in range(1,n+1):
    for k in range(n+1):
        for j in range(n*A+1):
            if 1<=k<=i and 0<=j-x[i-1]:
                dp[i,k,j]=dp[i-1,k,j]+dp[i-1,k-1,j-x[i-1]]
            else:
                dp[i,k,j]=dp[i-1,k,j]
c=0
for k in range(1,n+1):
    c+=dp[n,k,k*A]
print(c)


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

prime =[2]
for i in range(2,max_l+1):
    for j in prime:
        if i % j == 0:
            break
        else:
            if j == prime[-1]:
                prime.append(i)

p = 0
count = {}
for i in range(1,max_l+2,2):
    if (i in prime) and ((i+1)/2 in prime):
        p += 1
    count[i] = p
count[-1] = 0
for i in range(Q):
    print(count[lr[i][1]]-count[lr[i][0]-2])


### FIXED CODE ###

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print(like2017[lr[i][1]]-like2017[lr[i][0]-2])
### BUGGY CODE ###

def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    checked = [False] * n
    checked[0] = True
    return sum(dfs(0)) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い


### FIXED CODE ###

def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

    dp_w = [1] * n
    dp_b = [1] * n

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い
### BUGGY CODE ###

import numpy as np


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


K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            total += gcd(gcd(i, j), k)

print(total)


### FIXED CODE ###

import math as f

K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        ij = f.gcd(i, j)
        if ij == 1:
            total += K
            continue
        for k in range(1, K + 1):
            total += f.gcd(ij, k)

print(total)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
from functools import lru_cache

import math

@lru_cache(maxsize=None)
def combi(n,r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

max_combi = 0
l=0
for r in range(1,n):

    while a[l] <= (a[r]+1)//2:
        l+=1
    l-=1
    
    c = combi(a[r], a[l])
    if c > max_combi:
        max_combi = c
        x,y = a[r], a[l]

print(x,y)


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))

import bisect

mid = (a[-1]+1)//2
mid_idx = bisect.bisect_left(a, mid)

if abs(mid - a[mid_idx-1]) <= abs(a[mid_idx] - mid):
    print(a[-1], a[mid_idx-1])
else:
    print(a[-1], a[mid_idx])
### BUGGY CODE ###

n,mondaisuu=map(int,input().split())
s=input()
li=[0]*n
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    li[i]=1
for i in range(mondaisuu):
  l,r=map(int,input().split())
  print(sum(li[l-1:r-1]))

### FIXED CODE ###

n,mondaisuu=map(int,input().split())
s=input()
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1] + (1 if s[i]=="C" and s[i-1]=="A" else 0)
for i in range(mondaisuu):
  l,r=map(int,input().split())
  print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

import numpy as np
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, q = map(int, readline().split())
s = readline().rstrip()
for _ in range(q):
	l, r = map(int, readline().split())
	l -= 1
	r -= 1
	ans = 0
	for i in range(l, r):
		if s[i] == 'A' and s[i + 1] == 'C':
			ans += 1
	print(ans)



### FIXED CODE ###

import numpy as np
import sys
readline = sys.stdin.readline
read = sys.stdin.read

import bisect
n, q = map(int, readline().split())
s = readline().rstrip()
a = []
for i in range(len(s) - 1):
	if s[i] == 'A' and s[i + 1] == 'C':
		a.append(i)
for _ in range(q):
	l, r = map(int, readline().split())
	l -= 1
	r -= 2
	print(bisect.bisect_right(a, r) - bisect.bisect_left(a, l))
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
grid = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        grid[i][j] = abs(A[i][j] - B[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(grid[0][0])

for i in range(H):
    for j in range(W):
        for k in dp[i][j]:
            if i < H - 1:
                nk = grid[i + 1][j]
                dp[i + 1][j].add(k + nk)
                dp[i + 1][j].add(abs(k - nk))
            if j < W - 1:
                nk = grid[i][j + 1]
                dp[i][j + 1].add(k + nk)
                dp[i][j + 1].add(abs(k - nk))

print(min(dp[-1][-1]))


### FIXED CODE ###

H, W = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        here = dp[i][j]
        s = Diff[i][j]
        ni = 0
        nj = 0
        ni |= (here << s)
        nj |= (here << s)
        ni |= (here >> s)
        nj |= (here >> s)
        ex = 0
        for k in range(1, s + 1):
            if (here >> k) & 1:
                ex |= (1 << (s - k))
        ni |= ex
        nj |= ex
        dp[i + 1][j] |= ni
        dp[i][j + 1] |= nj

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)
### BUGGY CODE ###

n=int(input())
a=map(int,input().split())

b = [ (a,i) for i,a in enumerate(a)]

b.sort(reverse=True)

dp=[ [0] * (n+1) for i in range(n+1) ]

ans=0

for l in range(n):
  for r in range(n):
    if l + r == n:
      ans = max( ans, dp[l][r] )
      break
    act , i = b[l+r]
    dp[l+1][r] = max( dp[l+1][r] , dp[l][r] +act*abs(i-l))
    dp[l][r+1] = max( dp[l][r+1] , dp[l][r] +act*abs(n-i-1-r))
print(ans)

### FIXED CODE ###

n=int(input())
a=map(int,input().split())

b = [ (a,i) for i,a in enumerate(a)]

b.sort(reverse=True)

dp=[ [0] * (n+1) for i in range(n+1) ]

ans=0

for l in range(n):
  for r in range(n):
    if l + r == n:
      ans = max( ans, dp[l][r] )
      break
    act , i = b[l+r]
    dp[l+1][r] = max( dp[l+1][r] , dp[l][r] +act*abs(i-l))
    dp[l][r+1] = max( dp[l][r+1] , dp[l][r] +act*abs(n-i-1-r))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

# from numba import njit

# input = stdin.readline

# @njit
def solve(k,s):
  res = 0
  for i in range(k+1):
    for j in range(k+1):
      for l in range(k+1):
        if i+j+l == s:
          res += 1

  return res



def main():
  K,S = map(int,input().split())
  # a = list(map(int,input().split()))
  print(solve(K,S))
  return

if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python3

# from numba import njit

# input = stdin.readline

# @njit
def solve(k,s):
  res = 0
  for i in range(k+1):
    for j in range(k+1):
      l = s - i - j
      if 0 <= l <= k:
        res += 1

  return res



def main():
  K,S = map(int,input().split())
  # a = list(map(int,input().split()))
  print(solve(K,S))
  return

if __name__ == '__main__':
  main()
### BUGGY CODE ###

size, jumps = map(int, input().split())
array = list(map(int, input().split()))
dp = [9999999999] * size
dp[0]= 0
for i in range(size):
    for j in range(i + 1, i+jumps+1):
        if j < size:
            dp[j] = min(dp[j], dp[i]+abs(array[i] - array[j]))
print(dp[size-1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

#input
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    C[i] = list(map(int, input().split()))

#output
dp = [9**9]* (1<<N)

def list_to_bin(my_list):
    my_bin = 0
    for l in my_list:
        my_bin += 1<<(l-1)
    return my_bin

dp[0] = 0
for i in range(M):
    for s in range(1<<N):
        dp[s|list_to_bin(C[i])] = min(dp[s|list_to_bin(C[i])], dp[s] + A[i])

if dp[-1] == 9**9:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

#input
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    C[i] = list(map(int, input().split()))

#output
dp = [9**9]* (1<<N)

def list_to_bin(my_list):
    my_bin = 0
    for l in my_list:
        my_bin += 1<<(l-1)
    return my_bin

for i in range(M):
    C[i] = list_to_bin(C[i])

dp[0] = 0
for i in range(M):
    for s in range(1<<N):
        dp[s|C[i]] = min(dp[s|C[i]], dp[s] + A[i])

if dp[-1] == 9**9:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

n,k=map(int, input().split())
a= list(map(int, input().split()))
maxans=0
for i in range(len(a)):
  ans=sum(a[i:i+k])
  maxans=max(ans,maxans)
print((maxans+k)/2)

### FIXED CODE ###

n,k=map(int, input().split())
a= list(map(int, input().split()))
l=[]
for i in range(len(a)):
  l.append((a[i]+1)/2)
maxans=sum(l[0:k])
ans=sum(l[0:k])
for i in range(len(l)-k):
  ans=ans+l[i+k]-l[i]
  maxans=max(ans,maxans)
 
print(maxans)
### BUGGY CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]



N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ans = 0

A.sort()
B.sort()
C.sort()


for i in range(N):
  temp = bisect.bisect_left(B, A[i]+1)
  for j in range(temp, N):
    ans += (N-bisect.bisect_left(C, B[j]+1))


print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]



N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
AA = [0]*N
BB = [0]*N
ans = 0

A.sort()
B.sort()
C.sort()


for i in range(N):
  AA[i] = bisect.bisect_right(A, B[i]-1)

for j in range(N):
  BB[j] = bisect.bisect_left(C, B[j]+1)

for k in range(N):
  ans += AA[k]*(N-BB[k])

print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
w = [s[:i+1].count("W") for i in range(n)]
e = [s[:i+1].count("E") for i in range(n)]

ans = e[-1]
for i in range(1,n):
  ans = min(ans, w[i-1]+e[-1]-e[i])
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
w = []
c = 0
for i in range(n):
  if s[i] == "W":
    c += 1
  w.append(c)
e = [i+1-w[i] for i in range(n)]
ans = e[-1]
for i in range(1,n):
  ans = min(ans, w[i-1]+e[-1]-e[i])
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())

    s = list(''.join(sorted(input()[:])) for i in range(n))

    count = 0
    for i in range(0, n):
        count += s[i+1:].count(s[i])

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())

    count = 0
    found = {}
    for _ in range(n):
        str = ''.join(sorted(input()))
        if str in found:
            count += found[str]
            found[str] += 1
        else:
            found[str] = 1

    print(count)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            nj = min(j+A[i], half+1)
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][nj] = (dp1[i+1][nj] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][nj] = (dp2[i+1][nj] + dp2[i][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
a = np.array(a)
ret = []
for i in range(N):
    ind = np.ones(N, dtype=bool)
    ind[i] = False
    tmp = a[ind]
    ret.append(np.median(tmp))
for rett in ret:
  print(int(rett))

### FIXED CODE ###

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
sort_a = sorted(a)
small = sort_a[N//2-1]
big = sort_a[N//2]
for aa in a:
    if aa < big:
        print(big)
    else:
        print(small)
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        ans+=1


print(ans)  

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
a=p[0]
for i in range(n):
    if p[i] <= a:
        ans+=1
    
    a=min(a,p[i])    


print(ans)
### BUGGY CODE ###

import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))

for _ in range(min(K,200)):
    imos = np.zeros(N+1,int)
    for i in range(N):
        l, r = max(i-A[i],0), min(i+A[i],N-1)
        imos[l] += 1
        imos[r+1] += -1
    
    A = np.cumsum(imos)[:N]

for a in A:
    print(a, end=" ")
print()



### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(K):
    flag = True
    for a in A:
        if a != N: flag = False
    if flag: break

    imos = [0] * (N+1)
    for i in range(N):
        l = max(i-A[i],0)
        r = min(i+A[i],N-1)
        imos[l] += 1
        imos[r+1] += -1
    
    for i in range(N):
        imos[i+1] += imos[i]
    
    A = imos[:N]

for a in A[:N]:
    print(a, end=" ")
print()
### BUGGY CODE ###

#%%

#%%
n = int(input())

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range((len(c)+1)//2):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    if a == b:
        break
    

print(k-2)


### FIXED CODE ###

#%%
n = int(input())
a = 10**15


x = int(n**0.5)
x += 1
for i in range(x, 1, -1):
    if n%i == 0:
        a = i
        b = n//i
        break
#print(a, b)

if a == 10**15:
    print(n-1)
else:
    print(a+b-2)