Harryxun/stf_run huggingface dataset:
# 09-Computation-Min_Max_and_Sum.py

# ????°????????????§??????????¨????
# n ????????´??° ai(i=1,2,...n)?????\?????????????????????????°????????????§??????????¨????????±???????????????°????????????????????????????????????

# Input
# ??????????????´??°?????° n ???????????????????????????????????? n ????????´??° ai ????????????????????§?????????????????????
# Output
# ????°????????????§??????????¨????????????????????????§????????????????????????????????????

# Constraints
# 0<n???10000
# ???1000000???ai???1000000
# Sample Input
# 5
# 10 1 5 4 17
# Sample Output
# 1 17 37

num = int(input())
num_min = 1000001
num_max = -1000001
num_sum = 0

# a = []
# a = [ *map(int,input().split() ) ]


for i in range(num):
	if a[i]<num_min:
		num_min = a[i]

	if a[i]>num_max:
		num_max = a[i]

	num_sum+=a[i]

print("{0} {1} {2}".format(num_min,num_max,num_sum) );

### FIXED CODE ###

# 09-Computation-Min_Max_and_Sum.py

# ????°????????????§??????????¨????
# n ????????´??° ai(i=1,2,...n)?????\?????????????????????????°????????????§??????????¨????????±???????????????°????????????????????????????????????

# Input
# ??????????????´??°?????° n ???????????????????????????????????? n ????????´??° ai ????????????????????§?????????????????????
# Output
# ????°????????????§??????????¨????????????????????????§????????????????????????????????????

# Constraints
# 0<n???10000
# ???1000000???ai???1000000
# Sample Input
# 5
# 10 1 5 4 17
# Sample Output
# 1 17 37

num_min = 1000001
num_max = -1000001
num_sum = 0
num = int(input())

# a = []
# a = [ *map(int,input().split() ) ]
a = input().split()

for i in range(num):
	a[i]=int(a[i])
	if a[i]<num_min:
		num_min = a[i]

	if a[i]>num_max:
		num_max = a[i]

	num_sum+=a[i]

print("{0} {1} {2}".format(num_min,num_max,num_sum) );
for i in range(1, 10):
    for j in range(1, 10):
        print(i + "x" + j + "=" + i * j)

### FIXED CODE ###

for i in range(1, 10):
    for j in range(1, 10):
        print("{}x{}={}".format(i, j, i*j))
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)

### FIXED CODE ###

N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)
A,B,C,X=map(int,input() for i in range(4))
ans=0
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if i*500+j*100+k*50==X:
        ans+=1
print(ans)        
      

### FIXED CODE ###

A,B,C,X=map(int,[input() for i in range(4)])
ans=0
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if i*500+j*100+k*50==X:
        ans+=1
print(ans)
print int(raw_input())**3

### FIXED CODE ###

i=int(raw_input())
print i**3
# クエリはまとめてしまえ

n, q = map(int, input().split())
ki = [[] for i in range(n)]

def union(a, b):
  # aの子供
  ki[a].append(b)

for i in range(n-1):
  a, b = map(int, input().split())
  union(a-1, b-1)

table = {}
for _ in range(q):
  p, x = map(int, input().split())
  if p-1 not in table:
    table[p-1] = x
  else:
    table[p-1] += x
ans = [0 for _ in range(n)]


def f(k, v, b):
  if len(ki[k])>0:
    # 自分自身
    if b == False:
      ans[k] += v
    for x in ki[k]:
      ans[x] += v
    for x in ki[k]:
      # 再起するときのマーク
      f(x, v, True)
  else:
    if b == False:
      ans[k] += v
for k, v in table.items():
  f(k, v, False)

print(" ".join(list(map(str, ans))))

### FIXED CODE ###

# 木全体の根が決まっているのでふつうにbfsでいい気がするが...
# 毎回探索するんじゃなくて、各枝にポイントをつけておいて、探索するときに1回だけ渡して更新していく
# 考え方は累積和
# なんかafter_contestってテストケースでハネられるんだが。。。。。なんだこれ
# i<jのときiのほうが根に近い、というのを決め打ちしても通ってしまう防止らしい
# 回避するべく
# 両方のノードからエッジを貼り(graph[b].append(a))、
# 探索のときに訪問済みの場所は抜くことにした(if node not in used:)

n, q = map(int, input().split())
graph = [[] for _ in range(n)]
points = [0 for _ in range(n)]

for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    points[p - 1] += x

path = [0]
used = set()
used.add(0)
while len(path) > 0:
    cur_node = path.pop()
    cur_point = points[cur_node]
    for node in graph[cur_node]:
        if node not in used:
            used.add(node)
            points[node] += cur_point
            path.append(node)
print(" ".join(list(map(str, points))))
import math
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

for p in range(1, 4):
 sum = 0
 for i in range(n):
  sum += math.fabs(x[i]-y[i])**p
 print(sum**(1/p))

a = []
for i in range(n):
 a.append(math.fabs(x[i]-y[i]))
a = a.sort()
print(a[n-1])

### FIXED CODE ###

import math
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

for p in range(1, 4):
 sum = 0
 for i in range(n):
  sum += math.fabs(x[i]-y[i])**p
 print(sum**(1/p))

a = []
for i in range(n):
 a.append(math.fabs(x[i]-y[i]))
a.sort()
print(a[n-1])
#!/usr/bin/env python3
import sys
input = sys.stdin.readline


n = int(input())
a = [int(item) for item in input().split()]
prev = a[0]
a_uniq = [a[0]]
for item in a:
    if item == prev:
        continue
    a_uniq.append(item)
    prev = item

increasing = None
if a_uniq[0] < a_uniq[1]:
    increasing = True
else:
    increasing = False

money = 1000
kabu = 0
if increasing:
    p = money // a[0]
    money -= p * a[0]
    kabu = p

prev = a_uniq[0]
ans = 1000
for item in a_uniq[1:]:
    if item < prev and increasing:
        money += kabu * prev
        kabu = 0
        increasing = False
        ans = max(ans, money)
    if item > prev and not increasing:
        p = money // prev
        money -= p * prev
        kabu = p
        increasing = True
    prev = item
if kabu:
    money += a_uniq[-1] * kabu
    ans = max(ans, money)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline


n = int(input())
a = [int(item) for item in input().split()]
prev = a[0]
a_uniq = [a[0]]
for item in a:
    if item == prev:
        continue
    a_uniq.append(item)
    prev = item

if len(a_uniq) == 1:
    print(1000)
    exit()

increasing = None
if a_uniq[0] < a_uniq[1]:
    increasing = True
else:
    increasing = False

money = 1000
kabu = 0
if increasing:
    p = money // a[0]
    money -= p * a[0]
    kabu = p

prev = a_uniq[0]
ans = 1000
for item in a_uniq[1:]:
    if item < prev and increasing:
        money += kabu * prev
        kabu = 0
        increasing = False
        ans = max(ans, money)
    if item > prev and not increasing:
        p = money // prev
        money -= p * prev
        kabu = p
        increasing = True
    prev = item
if kabu:
    money += a_uniq[-1] * kabu
    ans = max(ans, money)
print(ans)
from collections import defaultdict 
import sys
import math 
import random
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


def r(ind):
    if dp[ind]!=-1:
        return dp[ind]
    if ind+1>=n:
        return 0
    ans1 = abs(a[ind+1]-a[ind])+r(ind+1)
    if ind+2>=n:
        dp[ind] = ans1 
        return dp[ind] 
    ans2 = abs(a[ind+2]-a[ind])+r(ind+2)
    dp[ind] = min(ans1,ans2)
    return dp[ind]

n = int(input())
a = get_array()
dp = [-1]*(n+5) 
print(r(0))


### FIXED CODE ###

from collections import defaultdict 
import sys
import math 
import random
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10**5)

def r(ind):
    if dp[ind]!=-1:
        return dp[ind]
    if ind+1>=n:
        return 0
    ans1 = abs(a[ind+1]-a[ind])+r(ind+1)
    if ind+2>=n:
        dp[ind] = ans1 
        return dp[ind] 
    ans2 = abs(a[ind+2]-a[ind])+r(ind+2)
    dp[ind] = min(ans1,ans2)
    return dp[ind]

n = int(input())
a = get_array()
dp = [-1]*(n+5) 
print(r(0))
list = input().split
l = list(map(int,list))
a =l[0]
b =l[1]

if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')


### FIXED CODE ###

l = map(int,input().split())
l = list(l)
a =l[0]
b =l[1]

if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
N,M=map(int,input().split())
a=[]
for _ in [0]*M:
    a.append(int(input()))

stepsum=[1]   #k段目までの組み合わせ
if a[0]==1:   #1段目がNGなら
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in range(2,N+1):
    stepsum.append((stepsum[i-1]+stepsum[i-2])*(not(i in a)))

ans=stepsum[N]%1000000007
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
a=[]
for _ in [0]*M:
    a.append(int(input()))

a.append(N+1)    

step=[]

if a[0]==1:j=1
else:j=0

for i in range(2,N+1):
    if i <a[j]:
        step.append(i)
    else:
        step.append(0)
        j+=1

stepsum=[1]   #k段目までの組み合わせ
if a[0]==1:   #1段目がNGなら
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in step:
    if i==0:stepsum.append(0)
    else:stepsum.append(((stepsum[i-1]+stepsum[i-2]))%1000000007)


ans=stepsum[N]%1000000007
print(ans)
import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            next = collections.deque()
            dist = []
            checked = []
            curmax = 0
            for k in range(h):
                a = [0]*w
                b = [0]*w
                dist.append(a)
                checked.append(b)
            next.append([i,j])
            while len(next) != 0:
                cur = next.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                next.append([t,u])
                                curmax = max(curmax,dist[t][u])
        ans = max(ans,curmax)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)
N, M, X, Y = map(int, input().split())
a = list(map(int, input().split()))
for i in range(M):
    if(i == 0):
        mx= a[i]
    else:
        mx = max(a[i],mx)
a = list(map(int, input().split()))
if(mx >= Y):
    print("War")
    quit()
for i in range(M):
    if(i == 0):
        my = a[i]
    else:
        my = min(a[i],my)
if(my <= X):
    print("War")
    quit()
if(mx >= my):
    print("War")
else:
    print("No War")


### FIXED CODE ###

n,m,a,b = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x = max(x)
y = min(y)
for z in range(x+1,y+1):
    if a < z and z <= b:
        print("No War")
        quit()
print("War")
N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(N-1):
   while a[i]+a[i+1] > x:
       if a[i]>a[i+1]:
           a[i] -= 1
          count += 1
      else:
           a[i+1] -= 1
           count += 1

print(count)

### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(N-1):
    while a[i]+a[i+1] > x:
        if a[i]>x:
           count += a[i]-x
           a[i] = x
        else:
           count += a[i+1] - (x-a[i])
           a[i+1] = x - a[i]

print(count)
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###


def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()
a,b = map(int,input().split())
N = list(map(int,input().split()))
N.sort()
for i in range(b):
    N.pop()
print(sum(N))

### FIXED CODE ###

a,b = map(int,input().split())
N = list(map(int,input().split()))
N.sort()
for i in range(b):
    if N:
        N.pop()
print(sum(N))
N,A = map(int,input().split())
X = [0]+list(map(int,input().split()))

maxX = max(X)
dp = [[[0 for _ in range(N*maxX+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(0,i+1):
        for k in range(N*maxX+1):
            if j==0 and k==0:
                dp[i][j][k] = 1
            elif k < X[i]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j > 0 and k >= X[i]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i]]

Ans = 0
for i in range(1,N+1):
    Ans += dp[N][i][A*i]

print(Ans)

### FIXED CODE ###

N,A = map(int,input().split())
X = [0]+list(map(int,input().split()))

dp = [[[0 for _ in range(2500+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(0,i+1):
        for k in range(2500+1):
            if j==0 and k==0:
                dp[i][j][k] = 1
            elif k < X[i]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j > 0 and k >= X[i]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i]]

if max(X) < A:
    print(0)
else:
    Ans = 0
    for i in range(1,N+1):
        Ans += dp[N][i][A*i]
    print(Ans)
a=input()
b=input()
c=input()
d=input()
e=input()
k=input()
print('Yay!' if (e-a)<=k else ':(')


### FIXED CODE ###

a=int(input())
b=input()
c=input()
d=input()
e=int(input())
k=int(input())
print('Yay!' if (e-a)<=k else ':(')
N = input()
A = input()

A_list = [A[i: i + 1] for i in range(0, len(A), 1)]

A_list_int = list(map(int, A_list))

max = max(A_list_int)
min = min(A_list_int)

print(max - min)

### FIXED CODE ###

N = input()
A_list = input().split()

A_list_int = list(map(int, A_list))

max = max(A_list_int)
min = min(A_list_int)

print(max - min)
a,b=(int(x) for x in input().split())
if a > b:
  while i < b:
    print(count(a))
else:
  while i < a:
    print(count(b))

### FIXED CODE ###

a,b=(int(x) for x in input().split())
i = 0
if a > b:
  while i < a:
    print(str(b), end="")
    i += 1
else:
  while i < b:
    print(str(a), end="")
    i += 1
s = input()
K = int(input())
 
li = sorted(list(set(s)))
result = []

def substring(l):
    result.append(l)
    if len(result) >= K:
        pass
    for m in li:
        if l+m in s:
            return substring(l+m)

for l in li:
    substring(l)

print(result[K-1])

### FIXED CODE ###

s = input()
K = int(input())
 
li = sorted(list(set(s)))
result = []

def substring(l):
    result.append(l)
    if len(result) < K:
        for m in li:
            if l+m in s:
                return substring(l+m)
    else:
        pass

for l in li:
    substring(l)

print(result[K-1])
def search_add_num(p,x):
    for k in ki[p]:
        if k!=p:
            search_add_num(k,x)
        else:
            k_values[p] += x
N,Q = map(int, input().split())
ki = [[i] for i in range(N+1)]
k_values = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b = map(int, input().split())
    ki[a].append(b)
for _ in range(Q):
    p,x = map(int, input().split())
    search_add_num(p,x)
print(' '.join(map(str, k_values[1:])))

### FIXED CODE ###

N,Q = map(int, input().split())
ki = [[] for i in range(N+1)]
val = [0 for _ in range(N+1)]

for _ in range(N-1):
  a,b = map(int, input().split())
  ki[a].append(b)
  ki[b].append(a)
for _ in range(Q):
  p,x = map(int, input().split())
  val[p] += x

q = [(1,0)]
while q:
  c,p = q.pop()
  val[c] += val[p]
  for x in ki[c]:
    if x==p:
      continue
    q.append((x,c))
print(' '.join(map(str, val[1:])))
N = int(input().splice()[0])
L = int(input().splice()[1])
Ss = []

for i in range(N):
  Ss[i] = input()

for i, a in enumerate(Ss):
  key = a
  j = i - 1

  while j >= 0 and Ss[j] > a:
    Ss[j + 1] = Ss[j]
    j = j - 1

  Ss[j + 1] = key

print(' '.join(Ss))

### FIXED CODE ###

N, L = map(int, input().split())
S = []
for i in range(N):
    line = input()
    S.append(line)
S.sort()
print("".join(S))
import numpy as np

MOD = 10**9+7

n = int(input())

### FIXED CODE ###

import numpy as np

MOD = 10**9+7

n = int(input())
arr = np.zeros((n+1,n+1), dtype=int)
for i in np.arange(3,n+1):
    arr[0,i] = 1

for i in np.arange(1,n+1):
    sum_ = 0
    for j in np.arange(3*i,n+1):
        sum_ += arr[i-1,j]
        sum_ %= MOD
        if j+3 >= n + 1:
            break
        arr[i,j+3] = sum_

ans = 0
for i in range(n+1):
    ans += arr[i,n]
    ans %= MOD
print(ans)
n, k = map(int, input().split())
p = sorted(map(int, input().split()))
print(sum([:k]))

### FIXED CODE ###

n, k = map(int, input().split())
p = sorted(map(int, input().split()))
print(sum(p[:k]))
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(0,n) :
    A = list(int,input().split())
    Sum = C
    for (x,y) in zip(A,B):
        Sum += (x*y)
    if wa > 0 :
        ans += 1
print(ans)

### FIXED CODE ###

N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(0,N) :
    A = list(map(int,input().split()))
    Sum = C
    for (x,y) in zip(A,B):
        Sum += (x*y)
    if Sum > 0 :
        ans += 1
print(ans)
N = int(input())
A = list(map(int, input().split()))
import numpy as np
import sys

if 0 in A:
    print(0)
    sys.exit()

ans = np.prod(A)
if ans<= 10**18:
    print(ans)
    sus.exit()
if 10**18 < ans:
    print(-1)


### FIXED CODE ###

A, B = map(int,input().split())
print(A*B)
x = int(input())

for a in range(1, x):
    for b in range(-a, a):
        if pow(a, 5) - pow(b, 5) == x:
            break
print(a, b)

### FIXED CODE ###

x = int(input())

for a in range(1, 120):
    for b in range(-a, a):
        if pow(a, 5) - pow(b, 5) == x:
            break
    if pow(a, 5) - pow(b, 5) == x:
         break
            
print(a, b)
a,b,c = [int(input()) for i in range(3)]
if a<b and b<c:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a,b,c = map(int,input().split())
if a<b and b<c:
    print('Yes')
else:
    print('No')
n,m=map(int,input().split())
lists_A=sorted(list(map(int,input().split())))
lists_BC=[]
sumk=0
for _ in range(m):
    while sumk<n+1:
        k,l=map(int,input().split())
        sumk+=k
        lists_BC=lists_BC+[l]*k
lists_BC=sorted(lists_BC)
listsBC=lists_BC[-min(n,sumk):]
listsBC=sorted(listsBC,reverse=True)
#listsBCの左のタプルから順にlistsAについて適用していく。
#listA内のインデックス
indexcheck=0
tupleindex=0
maxi=sum(lists_A)
for _ in range(min(n,sumk)):
    a=maxi+listsBC[_]-lists_A[_]
    if a>maxi:
        maxi=a
    else:
        continue      
print(maxi)

### FIXED CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
checklist=[]
count=0

for i in range(m):
    b,c=map(int,input().split())
    checklist.append((c,b))
checklist=sorted(checklist,reverse=True)
lists=sorted(lists)
uselist=[]
count=0

for i in checklist:
    for _ in range(i[1]):
        uselist.append(i[0])
    count+=i[1]

    if count>=n:
        break
answer=0
n=min(n,len(uselist))
for i in range(n):
    if lists[i]<uselist[i]:
            lists[i]=uselist[i]
    else:
        break
print(sum(lists))
vN,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
elif K<b and d == 0 and K%2 == 1:
    print(0)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)