Harryxun/stf_run huggingface dataset:
line = input()
N, M, X = [int(v) for v in line.split(" ")]

Ci, Aij = [], []
for i in range(N):
    line = input().split(" ")
    line = [int(v) for v in line]

    Ci.append(line[0])
    Aij.append(line[1:])

ans = []
def dfs(candidate):
    if len(candidate) == M:
        X_ = [0 for _ in range(M)]
        cost = 0
        for i in range(N):
            if candidate[i] == 0:
                continue
            cost += Ci[i]
            for j in range(M):
                X_[j] += Aij[i][j]
        if min(X_) >= X:
            ans.append(cost)
    else:
        for bit in range(2):
            candidate.append(bit)
            dfs(candidate)
            candidate.pop()

dfs([])
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

### FIXED CODE ###

line = input()
N, M, X = [int(v) for v in line.split(" ")]

Ci, Aij = [], []
for i in range(N):
    line = input().split(" ")
    line = [int(v) for v in line]

    Ci.append(line[0])
    Aij.append(line[1:])

ans = []
def dfs(candidate):
    if len(candidate) == N:
        X_ = [0 for _ in range(M)]
        cost = 0
        for i in range(N):
            if candidate[i] == 0:
                continue
            cost += Ci[i]
            for j in range(M):
                X_[j] += Aij[i][j]
        if min(X_) >= X:
            ans.append(cost)
    else:
        for bit in range(2):
            candidate.append(bit)
            dfs(candidate)
            candidate.pop()

dfs([])
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))
import itertools
N, M ,Q = map(int, input().split())
l = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  l.append([a, b, c, d])
  
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
nums = list(itertools.combinations_with_replacement(nums, 10))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]]-row[l[i][0]] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))

### FIXED CODE ###

import itertools
N, M ,Q = map(int, input().split())
l = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  l.append([a, b, c, d])
  
nums = list(itertools.combinations_with_replacement(range(1, M+1), N))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]-1]-row[l[i][0]-1] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))
# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

used = [False]*n
used[0] = True

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1,b-1] = 1
    graph[b-1,a-1] = 1

used = [False]*n
used[0] = True

def DFS(v,used):
    global ans
    if all(used):
        ans += 1
        return 
    for i in range(n):
        if used[i]:
            continue
        if graph[i,v] == 0:
            continue
        used[i] = True
        DFS(i,used)
        used[i] = False
    return

ans = 0
DFS(0,used)

print(ans)
if raw_input() == 'H': print 'H' if raw_input() == 'H' else 'D'
else: print 'H' if raw_input() == 'D' else 'D'

### FIXED CODE ###

inp = raw_input().split()

if inp[0] == 'H': print 'H' if inp[1] == 'H' else 'D'
else: print 'H' if inp[1] == 'D' else 'D'
from math import gcd
def lcm(a,b): return a*b//gcd(a,b)

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

n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(t, ans)
print(ans)

### FIXED CODE ###

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

n = int(input())

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(t, ans)
print(ans)
c11, c12, c13 = map(int, list(input()))
c21, c22, c23 = map(int, list(input()))
if c11 == c23 and c12 == c21 and c13 == c21:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

c11, c12, c13 = list(input())
c21, c22, c23 = list(input())
if c11 == c23 and c12 == c22 and c13 == c21:
    print('YES')
else:
    print('NO')
A,B = map(int, input().split())
print(max([A+B, A−B, A×B]))

### FIXED CODE ###

A,B = map(int, input().split())
print(max(A+B,A-B,A*B))
from statistics import mean
from collections import Counter
n,a,b=map(int,input().split())
v=sorted(list(map(int,input().split())),reverse=True)
avg=mean(v[:a])
print(avg)

p=Counter(v[:a])[v[a]]
q=Counter(v)[v[a]]

def n_func(n):
    ans=1
    for i in range(1,n+1):ans=(ans*i)
    return ans

def nCr(n,r):
    return (n_func(n)//n_func(r))//n_func(n-r)

if v[0]==v[a]:
    print(sum([nCr(b,a+i) for i in range(0,b-a+1)]))
else:
    print(nCr(q,p))

### FIXED CODE ###

from statistics import mean
from collections import Counter
n,a,b=map(int,input().split())
v=sorted(list(map(int,input().split())),reverse=True)
avg=mean(v[:a])
print(avg)

p=Counter(v[:a])[v[a-1]]
q=Counter(v)[v[a-1]]

def n_func(n):
    ans=1
    for i in range(1,n+1):ans=(ans*i)
    return ans

def nCr(n,r):
    return (n_func(n)//n_func(r))//n_func(n-r)

if v[0]==v[a-1]:
    print(sum([nCr(q,a+i) for i in range(0,min(b,q)-a+1)]))
else:
    print(nCr(q,p))
import math
import collections


n = int(input())

inputlist = []

for i in range(n):
    inputlist.append("".join(sorted(list(input()))))

counter = collections.Counter(inputlist)

counter = dict(counter)

valuelist = list(map(int, counter.values()))

ans = 0

for i in valuelist:
    if i == 1:
        continue
    if i == 2:
        ans += 1
        continue
    if i == 3:
        ans += 3
        continue

    ans += math.factorial(i) / math.factorial(2) / math.factorial(i - 2)

print(ans)


### FIXED CODE ###

import collections
import math


n = int(input())

inputlist = []

for i in range(n):
    inputlist.append("".join(sorted(list(input()))))

counter = collections.Counter(inputlist)

counter = dict(counter)
valuelist = list(map(int, counter.values()))

ans = 0

for i in valuelist:
    if i == 1:
        continue
    if i == 2:
        ans += 1
        continue
    temp = math.factorial(i)
    temp /= math.factorial(i-2)
    temp = int(temp / 2)
    ans += temp

print(ans)
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

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

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

ans = 1
for a in sorted(A, reverse=True):
    ans *= a
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * n
for i in a:
    dp[i-1] = -1
if dp[1] >= 0 and dp[0] >= 0:
    dp[0] = 1
    dp[1] = 2
elif dp[1] == -1 and dp[0] >= 0:
    dp[0] = 1
elif dp[1] >= 0 and dp[0] == -1:
    dp[1] = 1
else:
    print(0)
    exit()
for j in range(2, n):
    if dp[j] >= 0:
        if dp[j-1] >= 0 and dp[j-2] >= 0:
            dp[j] = dp[j-1] + dp[j-2]
        elif dp[j-1] == -1 and dp[j-2] >= 0:
            dp[j] = dp[j-2]
        elif dp[j-1] >= 0 and dp[j-2] == -1:
            dp[j] = dp[j-1]
        else:
            print(0)
            exit()
print(dp[n-1] % (10**9+7))
        

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * n
for i in a:
    dp[i-1] = -1
if n == 1:
    if dp[0] == 0:
        print(1)
        exit()
    elif dp[0] == -1:
        print(0)
        exit()
if dp[1] >= 0 and dp[0] >= 0:
    dp[0] = 1
    dp[1] = 2
elif dp[1] == -1 and dp[0] >= 0:
    dp[0] = 1
elif dp[1] >= 0 and dp[0] == -1:
    dp[1] = 1
else:
    print(0)
    exit()
for j in range(2, n):
    if dp[j] >= 0:
        if dp[j-1] >= 0 and dp[j-2] >= 0:
            dp[j] = dp[j-1] + dp[j-2]
        elif dp[j-1] == -1 and dp[j-2] >= 0:
            dp[j] = dp[j-2]
        elif dp[j-1] >= 0 and dp[j-2] == -1:
            dp[j] = dp[j-1]
        else:
            print(0)
            exit()
print(dp[n-1] % (10**9+7))
import sys

class Node:
    def __init__(self, i):
        self.linked = list()
        self.id = i
        self.blocked = list()
        self.visited = False

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
nodes = [] 
for i in range(n):
    nodes.append(Node(i))

for i in range(m):
    line = sys.stdin.readline().strip()
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    nodes[a].linked.append(b)
    nodes[b].linked.append(a)

for i in range(k):
    line = sys.stdin.readline().strip()
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    nodes[a].blocked.append(b)
    nodes[b].blocked.append(a)

start = 0
res = [0] * n
while True:
    visited = [start]
    def deep_first(node):
        temp = []
        for one in node.linked:
            if not nodes[one].visited:
                visited.append(one)
                nodes[one].visited = True 
                temp.append(one)
        for one in temp:
            deep_first(nodes[one])

    nodes[start].visited = True
    deep_first(nodes[start])           
    for one in visited:
        cands = 0
        for two in nodes[one].blocked:
            if two in visited:
                cands += 1
        res[one] = len(visited) - len(nodes[one].linked) - 1 - cands

    start = -1
    for i in range(1, n):
        if not nodes[i].visited:
            start = i
            break
    if start == -1:
        break

print(" ".join(map(str, res)))

### FIXED CODE ###

import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = [-1]*n
linked = [0]*n
def find_root(x):
    if roots[x] < 0:
        return x
    else:
        roots[x] = find_root(roots[x])
        return roots[x]
def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if (x==y):
        return
    if roots[x] > roots[y]:
        c, d = y,x
        x,y = c,d
    roots[x] += roots[y]
    roots[y] = x

for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = a-1,b-1
    linked[c] += 1 
    linked[d] += 1
    unite(c,d)
#print(roots)
blacks = [[]for i in range(n)]
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    blacks[c].append(d)
    blacks[d].append(c)
res = []
for i in range(n):
    r = -roots[find_root(i)] - 1 - linked[i]
    for one in blacks[i]:
        if find_root(one) == find_root(i):
            r -= 1
    res.append(r)
    
print (" ".join(map(str, res)))
n = int(input())
print("Yes" if sum(map(int,n))%n==0 else "No")


### FIXED CODE ###

n = input()
print("Yes" if int(n)%sum(map(int,n))==0 else "No")
input_1, input_2 = [s for s in input().split()]

multiple = input_1 * input_2

judge = multiple % 2 

if judge ==0:
	print("Even")
elif:
	print("Odd")
  

### FIXED CODE ###

a,b = map(int,input().split())
 
if a*b % 2 == 1:
    print("Odd")
else:
    print("Even")
N = int(input())

idx_1st=1
val_1st=1
idx_2nd=0
val_2nd=0

for i in range(N):
  Ai = int(input())
  if Ai>=val_1st:
    idx_2nd=idx_1st
    val_2nd=val_1st
    
    idx_1st=i
    val_1st=Ai
    
  elif Ai<val_1st:
    if Ai>val_2nd:
      idx_2nd=i
      val_2nd=Ai
    else:
      raise ValueError
  else:
    raise ValueError

for i in range(N):
  if i!=idx_1st:
    print(val_1st)
  elif i==idx_1st:
    print(val_2nd)
  else:
    raise ValueError

### FIXED CODE ###

N = int(input())

idx_1st=1
val_1st=1
idx_2nd=0
val_2nd=0

for i in range(N):
  Ai = int(input())
  if Ai>=val_1st:
    idx_2nd=idx_1st
    val_2nd=val_1st
    
    idx_1st=i
    val_1st=Ai
    
  elif Ai<val_1st:
    if Ai>val_2nd:
      idx_2nd=i
      val_2nd=Ai
  else:
    raise ValueError

for i in range(N):
  if i!=idx_1st:
    print(val_1st)
  elif i==idx_1st:
    print(val_2nd)
  else:
    raise ValueError
N,M=map(int, input().split())
H=list(map(int, input().split()))
flag=[1]*N
for i in range(M):
    A,B=map(int, input().split())
    if H[A-1]>H[B-1]:
        flag[B-1]=0 
    elif H[A-1]<H[B-1]:
        flag[A-1]=0
    else:
        flag[A-1]=0
        flag[B-1]=0
print(sum(flag))

### FIXED CODE ###

# coding: utf-8
# Your code here!
input1 = input().rstrip()
if input1=="ABC":
    print("ARC")
elif input1=="ARC":
    print("ABC")
else:
    print(0)
n = int(input())
a = [int(x) for x in input().split()]

a2 = [a[i] - i - 1 for i in range(n)]
mean = sum(a2) / len(a2)
b = np.floor(mean)
a3 = sum([abs(a2[i] - b) for i in range(n)])
b = np.ceil(mean)
a4 = sum([abs(a2[i] - b) for i in range(n)])
print(int(min(a3, a4)))


### FIXED CODE ###

import numpy as np

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

a2 = [a[i] - i - 1 for i in range(n)]
mean = sum(a2) / len(a2)
median = np.median(np.array(a2))
b = np.floor(median)
a3 = sum([abs(a2[i] - b) for i in range(n)])
b = np.ceil(median)
a4 = sum([abs(a2[i] - b) for i in range(n)])
print(int(min(a3, a4)))
s = input()
k = int(input())

for i in range(len(s)):
    if s[i] == '1':
        continue
    else:
        break
if i == 0:
    print(s[0])
elif i < k:
    print(s[i + 1])
else:
    print(1)

### FIXED CODE ###

s = input()
k = int(input())

for i in range(len(s)):
    if s[i] == '1':
        continue
    else:
        break
if i == 0:
    print(s[0])
elif i < k:
    print(s[i])
else:
    print(1)
n=int(input())
a= list(map(int, input().split()))

dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
for i in range(2,n):
    dp[i][0]=dp[i-2][0]+a[i]
    if i>=3:
        dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
    if i>=4:
        dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i])

if n%2==0:
    print(max(dp[-2][0],dp[-1][1]))
else:
    print(max(dp[-3][0],dp[-2][1],dp[-1][2]))

### FIXED CODE ###

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=list(itertools.accumulate(a1))
a4=list(itertools.accumulate(a2))


x1=sum(a1)
x2=sum(a2)


if n%2==0:
    ans=-float('inf')
    for i in range(n//2):
        ans=max(a3[i]+x2-a4[i],ans)
    print(max(ans,x1,x2))
else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目までのMAX
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    # dp2[i]=奇数偶数or偶数のみと移動した時のi番目までのMAX
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i] + a2[i + 1], dp2[i] + a2[i + 1])
        if i==0:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))
from itertools import accumulate
N,K =map(int,input().split())
arr = [int(x) for x in input().split()]
ps = []
ms = []
for i in range(N):
    if arr[i] == 0:
        K -= 1
    elif arr[i] < 0:
        ms.append(abs(arr[i]))
    elif arr[i] > 0:
        ps.append(arr[i])
ms = ms[::-1]
if K == 0:
    ans = 0
else:
    ans = ps[K-1] if K <= len(ps) else 10**18
    ans = min(ans,ms[K-1]) if K <= len(ms) else ans
if len(ps) > 0 and len(ms) > 0:
    for i in range(K):
        if i == len(ms):
            break
        ans = min(ans,ms[i]*2 + ps[K-(i+1)-1])
    for i in range(K):
        if i == len(ps):
            break
        ans = min(ans,ps[i]*2 + ms[K-(i+1)-1])
print(ans)
    

### FIXED CODE ###

N, K = map(int, input().split())
arr = [int(x) for x in input().split()]
ps = []
ms = []
for i in range(N):
    if arr[i] == 0:
        K -= 1
    elif arr[i] < 0:
        ms.append(abs(arr[i]))
    elif arr[i] > 0:
        ps.append(arr[i])
ms = ms[::-1]
if K <= 0:
    ans = 0
else:
    ans = ps[K-1] if K <= len(ps) else 10**18
    ans = min(ans, ms[K-1]) if K <= len(ms) else ans
if len(ps) > 0 and len(ms) > 0:
    for i in range(len(ms)):
        if K-(i+1)-1 < len(ps):
            ans = min(ans, ms[i]*2 + ps[K-(i+1)-1])
    for i in range(len(ps)):
        if K-(i+1)-1 < len(ms):
            ans = min(ans, ps[i]*2 + ms[K-(i+1)-1])
print(ans)
a,b,c = input()
if(a + b < c):
    print(Yes)
else:
    print(No)

### FIXED CODE ###

a,b,c = map(int, input().split())
if a + b < c:
	print("No")
else:
	print("Yes")
n=int(input())
if n<=9:
  print(n)
elif n<=99:
  print(9)
elif n<=999:
  print(n-90):
elif n<=9999:
  print(909)
elif n==100000:
  print(90909)
else:
  print(n-9090)

### FIXED CODE ###

n=int(input())
if n<=9:
  print(n)
elif n<=99:
  print(9)
elif n<=999:
  print(n-90)
elif n<=9999:
  print(909)
elif n==100000:
  print(90909)
else:
  print(n-9090)
l = map(int, raw_input().split())
N = raw_input
l[0] = Q
l[1] = H
l[2] = S
l[3] = D
if Q*2 > H:
    M1 = H
else:
    M1 = Q*2

if  M1*2 > S:
    M = S
else:
    M = M1*2
if M*2 < D:
    print(M*N)
else:
    if N%2 == 0:
        print(D*(N//2))
    else:
        print(D*(N//2) + M)

### FIXED CODE ###

Q, H, S, D,= map(int, raw_input().split())
N = int(input())
if Q*2 > H:
    M1 = H
else:
    M1 = Q*2

if  M1*2 > S:
    M = S
else:
    M = M1*2
if M*2 < D:
    print(M*N)
else:
    if N%2 == 0:
        print(D*(N//2))
    else:
        print(D*(N//2) + M)
def gcd(a,b):
    r = a % b
    while r > 0:
        a = b
        b = r
        r = a % b
    return b

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

while True:
    try:
        a,b = map(int, raw_input().split())
        print gcd(a,b) + " " + lcm(a,b)
    except EOFError:
        break

### FIXED CODE ###

def gcd(a,b):
    r = a % b
    while r > 0:
        a = b
        b = r
        r = a % b
    return b

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

while True:
    try:
        a,b = map(int, raw_input().split())
        print str(gcd(a,b)) + " " + str(lcm(a,b))
    except EOFError:
        break
a, b, n = map(int, input().split())
current = 0
c = [0]*(n+1)
for x in range(n+1):
  c[x] = (a*x)//b - a*(x//b)
print(max(c))

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1,n)
print((a*x)//b - a*(x//b))
H, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

ans = 0

for i in range( N - K ):
  ans += A[i]
  
print(ans)

### FIXED CODE ###

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

A.sort()

ans = 0

for i in range( H - K ):
  ans += A[i]
  
print(ans)
a_index, a_v = map(int, input().split())
b_index, b_v = map(int, input().split())
t = input()
 
d = abs(b_index - a_index)
d_v = abs(b_v - a_v)
t_at = d / a_v
 
if (t_at < t) :
  print("YES")
else :
  print("NO")

### FIXED CODE ###

a_index, a_v = map(int, input().split())
b_index, b_v = map(int, input().split())
t = int(input())
 
d = abs(b_index - a_index)
d_v = a_v - b_v
 
if d == 0 :
  print("YES")
elif d_v > 0 and d / d_v <= t :
  print("YES")
else :
  print("NO")
s = input()
if s[0] == 'A' and s[2:-1].count('C') == 1 and s[:2].count('C') == 0 and s[-1:].count('C' == 0):
     list(s).remove("A")
     list(s).remove("C")
     print(s.islower())
     if s.islower() == 0:
          print("AC")
          exit()
else:
     print("WA")

### FIXED CODE ###

s = input()
ans = 'WA'
a = []
if s[0] == 'A' and s[2:-1].count('C') == 1:
     a = list(s)
     a.remove('A')
     a.remove('C')
     a = str(a)
     if a.islower() == True:
          ans = 'AC'
print(ans)
h1, m1, h2, m2. k = map(int, input().split())

time = h2 * 60 + m2 - h1 * 60 + m1
if k >= time:
    print(1)
else:
    print(time - k)

### FIXED CODE ###

h1, m1, h2, m2, k = map(int, input().split())
 
if h1 <= h2:
    time = h2 * 60 + m2 - h1 * 60 - m1
else:
    time = (h2+24) * 60 + m2 - h1 * 60 - m1
if k >= time:
    print(0)
else:
    print(time - k)
N,K = map(int,input().split())
l = [int(input())for i in range(N)]
l.sort()
L = l[(N-K):]
ans = sum(L)
print(ans)

### FIXED CODE ###

#ABC067.B
N,K = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
L = l[(N-K):]
ans = sum(L)
print(ans)
S=input()
ans=0
for i in range(2**(len(S)-1)):
    k=bin(i)[2:].zfill(len(S)-1)
    l=int(S[0])
    for j in range(len(k)):
        t=int(k[j])
        if t==1:
            ans+=l
            l=int(S[j+1])
        else:
            l=l*10+int(S[j+1])
    ans+=l
print(ans)


### FIXED CODE ###

import copy
S=input()
lst=[]
def Sum(l,S):
    if S=="A":
        return sum(l)
    a=l.pop()
    x=copy.copy(l)
    x.append(a*10+int(S[0]))
    y=copy.copy(l)
    y.extend([a,int(S[0])])
    return Sum(x,S[1:])+Sum(y,S[1:])
S+="A"
lst.append(int(S[0]))
print(Sum(lst,S[1:]))
N,K=map(int,input().split())
S=input()+"2"
_list=[]
if S[0]=="1":
    _list=[]
else:
    _list=[0]
cnt=1
for i in range(N):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        _list.append(cnt)
        cnt=1
if S[-2]=="0":
    _list.append(0)
import itertools
__list=[0]+list(itertools.accumulate(_list))
print(_list)
print(__list)
C=len(__list)
K=min(C,K)
if C//2==K:
    print(_list[0])
else:
    print(max([__list[2*i+2*K+1]-__list[2*i] for i in range(C//2-K)]))

### FIXED CODE ###

N,K = list(map(int,input().split()))
S = [int(i) for i in list(input())]
S.append(2)

S2 = []
cnt = 1
for i in range(N):
    if S[i] != S[i+1]:
        S2.append([S[i],cnt])
        cnt = 1
    else:
        cnt += 1

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    
    
SUM = [0]
for i in range(len(S2)):
    SUM.append(SUM[i] + S2[i][1])
T = []
for i in range(0,max(1,len(SUM)//2-K),1):
    T.append(SUM[min(len(SUM)-1,2*(K+i)+1)]-SUM[2*i])
print(max(T))
a,o,b = input().split()
a,b = map(int,(a,b))
print(a+b if o=='+': else a-b if o=='-': else a*b if o=='*': else a/b)


### FIXED CODE ###

while 1:
  s = input()
  if '?' in s:break
  print(int(eval(s)))
H = int(input())
W = int(input())
N = int(input())
for i in range(min(H,W)):
    N -= max(H, W):
    if N <= 0:
        print(i+1)

### FIXED CODE ###

H = int(input())
W = int(input())
N = int(input())
for i in range(min(H,W)):
    N -= max(H, W)
    if N <= 0:
        print(i+1)
        exit()
def 解():
    iN = int(input())
    aA = [int(_) for _ in input().split()]
    aA = reversed(sorted(aA))
    d = {}
    for a in aA:
        if a in d:
            if d[a] == 3:
                print(a*a)
                exit()
            elif iC and iC != a:
                print(iC * a)
                exit()
            else:
                iC = a
                d[a] += 1
        else:
            d[a] = 1
    print(0)
解()


### FIXED CODE ###

def 解():
    iN = int(input())
    aA = reversed(sorted([int(_) for _ in input().split()]))
    iC = 0
    d = {}
    for a in aA:
        if a in d:
            if d[a] == 3:
                print(a*a)
                exit()
            elif iC and iC != a:
                print(iC * a)
                exit()
            else:
                iC = a
                d[a] += 1
        else:
            d[a] = 1
    print(0)
解()
n=int(input())
ns=input().split()
for i in range(len(ns)):
    ns[i]=int(ns[i])
a=sum(ns)
i=min(ns)
u=max(ns)
print(amin,amax,asum)


### FIXED CODE ###

n=int(input())
ns=input().split()
for i in range(len(ns)):
    ns[i]=int(ns[i])
asum=sum(ns)
amin=min(ns)
amax=max(ns)
print(amin,amax,asum)
N = int(input())
A = map(int, input().split())
num = {}
ans = 1
mod = 1000000007
for a in A:
    s += str(a)
    if a == 0:
        if a not in num.keys():
            num[a] = 1
            ans *= 3 %mod
        else:
            if 1 not in num.keys():
                ans *= (3 - num[a]) %mod
            num[a] += 1
    else:
        if a not in num.keys():
            num[a] = 1
            ans *= num[a-1] %mod
            num[a-1] -= 1
        else:
            num[a] += 1
            ans *= num[a-1] %mod
            num[a-1] -= 1
    #print(s, num, ans%mod)
print(ans%mod)

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
num = {i:0 for i in range(N+1)}
num[0] = 3
ans = 1
MOD = 1000000007
for a in A:
    ans *= num[a] % MOD
    num[a] -= 1
    num[a+1] += 1
print(ans%MOD)