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

#!/usr/bin/env python3
import sys
from collections import defaultdict
rl = sys.stdin.buffer.readline
INF = sys.maxsize

N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
  n = n - ((n >> 1) & 0x5555555555555555)
  n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
  n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
  n = n + (n >> 8)
  n = n + (n >> 16)
  n = n + (n >> 32)
  return n & 0x0000007f

def subsets(s):
  t = s
  while t >= 0:
    t &= s
    yield t
    t -= 1

# (x|y)cost[i][j] := 頂点の集合 i に路線が引かれているとき、j 番目の集落から路線までの最小距離
xcost = defaultdict(lambda: defaultdict(lambda: INF))
ycost = defaultdict(lambda: defaultdict(lambda: INF))
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = abs(PS[j][0])
    ycost[i][j] = abs(PS[j][1])
    for k in range(N):
      if ((i >> k) & 1) == 1:
        xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
        ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))

# 計算結果の距離を歩行距離(= 距離 * 人口)にする
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = xcost[i][j] * PS[j][2]
    ycost[i][j] = ycost[i][j] * PS[j][2]

# x, y 座標に引かれた線路の引き方の組み合わせの中から最もコストが小さくなるものを求める
ans = [INF] * (N + 1)
for i in range(1 << N):
  size = bitcount(i)
  for j in subsets(i):
    cost = 0
    for k in range(N):
      # i に含まれていない頂点を合計する(i に含まれている頂点の歩行距離は常に０なので)
      if ((i >> k) & 1) == 0:
        cost += min(xcost[j][k], ycost[i-j][k])

    ans[size] = min(ans[size], cost)

# 結果出力
for a in ans:
  print(a)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
rl = sys.stdin.buffer.readline
INF = sys.maxsize

N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
  n = n - ((n >> 1) & 0x5555555555555555)
  n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
  n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
  n = n + (n >> 8)
  n = n + (n >> 16)
  n = n + (n >> 32)
  return n & 0x0000007f

def subsets(s):
  t = s
  while t >= 0:
    t &= s
    yield t
    t -= 1

# (x|y)cost[i][j] := 頂点の集合 i に路線が引かれているとき、j 番目の集落から路線までの最小距離
xcost = [[INF] * N for _ in range(1 << N)]
ycost = [[INF] * N for _ in range(1 << N)]
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = abs(PS[j][0])
    ycost[i][j] = abs(PS[j][1])
    for k in range(N):
      if ((i >> k) & 1) == 1:
        xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
        ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))

# 計算結果の距離を歩行距離(= 距離 * 人口)にする
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = xcost[i][j] * PS[j][2]
    ycost[i][j] = ycost[i][j] * PS[j][2]

# x, y 座標に引かれた線路の引き方の組み合わせの中から最もコストが小さくなるものを求める
ans = [INF] * (N + 1)
for i in range(1 << N):
  size = bitcount(i)
  for j in subsets(i):
    cost = 0
    for k in range(N):
      # i に含まれていない頂点を合計する(i に含まれている頂点の歩行距離は常に０なので)
      if ((i >> k) & 1) == 0:
        cost += min(xcost[j][k], ycost[i-j][k])

    ans[size] = min(ans[size], cost)

# 結果出力
for a in ans:
  print(a)
### BUGGY CODE ###

from pprint import pprint
from fractions import gcd
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return divisors
a, b = map(int, input().split())
cd = sorted(list(make_divisors(a) & make_divisors(b)))
n = len(cd)
divs = [[False for _ in range(n)] for _ in range(n)]
choice = []
answer = 0
for i in cd:
    n = len(choice)
    for j in range(n):
        for k in choice[j]:
            if gcd(i, k) != 1:
                break
        else:
            addition = choice[j] + [i]
            if len(addition) > answer:
                answer = len(addition)
            choice.append(addition)
    choice.append([i])
print(answer if answer > 0 else 1)

### FIXED CODE ###

from fractions import gcd
from math import sqrt
import sys
def input() -> str:
    return sys.stdin.readline()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return list(divisors)
def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
a, b = map(int, input().split())
print(len([div for div in make_divisors(gcd(a, b)) if is_prime(div)]) + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n, q = map(int, input().split())
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in d:
        d[a].append(b)
    else:
        d[a] = [b]
    if b in d:
        d[b].append(a)
    else:
        d[b] = [a]
d2 = {}
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    if p in d2:
        d2[p].append(x)
    else:
        d2[p] = [x]

ans = [0] * n

def dfs(cur, pre, point):
    if cur in d2:
        point += sum(d2[cur])
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join([str(item) for item in ans]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))
### BUGGY CODE ###

A, B, C, D, E, F = [int(i) for i in input().split()]
memo = {}

for a in range(31):
    for b in range(31):
        for c in range(101):
            for d in range(101):
                water = (100*A)*a + (100*B)*b
                sugar = C*c + D*d

                if (water + sugar) <= F and water > 0:
                    if sugar <= int(water*E/100):
                        density = 100*sugar/(water + sugar)
                        memo[density] = [water + sugar, sugar]

max_density = max(memo)
print(memo[max_density][0], memo[max_density][1])


### FIXED CODE ###

A, B, C, D, E, F = [int(i) for i in input().split()]
memo = {}

for a in range(31):
    for b in range(31):
        for c in range(101):
            for d in range(101):
                water = (100*A)*a + (100*B)*b
                sugar = C*c + D*d

                if (water + sugar) <= F and water > 0:
                    if sugar <= int(water*E/100):
                        density = 100*sugar/(water + sugar)
                        memo[density] = [water + sugar, sugar]

max_density = max(memo)
print(memo[max_density][0], memo[max_density][1])
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 'IMPOSSIBLE'
abl1 = []
abl2 = []
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.append(ab)
    elif ab[1] == N:
        abl2.append(ab)
    for i in abl1:
        if [i[1], N] in abl2:
            ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

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

#n = 7
#a = [3,1,4,1,5,9,2]
a2 = list(map(lambda x: x+1 , a)) #[4, 2, 5, 2, 6, 10, 3]
a3 = list(map(lambda x: x-1 , a)) #[2, 0, 3, 0, 4,  8, 1]

candi = {}
for i in a:
  candi[i],candi[i-1],candi[i+1] = 1,1,1

ans = 0
for i in candi.keys():
  count = (a.count(i) + a2.count(i) + a3.count(i))
  ans = max(count,ans)

print(ans)

### FIXED CODE ###

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

import collections
for i in range(n):
  a.append(a[i]+1)
  a.append(a[i]-1)

c = collections.Counter(a)
print(c.most_common()[0][1])
### BUGGY CODE ###

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

ans=0

for i in range(n):
  l=i+1
  for l in range(i+1,n):
   
    ans=ans+x[i]*x[l]
    
print(ans%1000000007)
  

### FIXED CODE ###

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

ans=0
total=0
t=sum(x)

for i in range(n):
 
  t=t-x[i]
  total=total+x[i]*(t)
  
   
    
print(total %1000000007)
### BUGGY CODE ###

from copy import copy
from collections import deque

N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

"""
N=10**5
M=10**5
ab=[]
for i in range(1,N):
    ab.append([i,i+1])
"""
AB=copy(ab)
ab.sort(key=lambda x :x[1])
AB.sort()
ab=deque(ab)
AB=deque(AB)
num=0
while(ab):
    p=ab.popleft()
    AB.remove(p)
    num+=1
    e=p[1]
    Q=copy(AB)
    for I in AB:
        if I[0]<e:
            Q.remove(I)
            ab.remove(I)
        else:
            break
    AB=Q
print(num)

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort(key=lambda x :x[1])
ans=deque()
for i in ab:
    if len(ans)>0:
        if i[0]<ans[-1] :
            continue
    ans.append(i[1])
print(len(ans))
### BUGGY CODE ###

N = int(input())
data = [i for i in input().split()]

number_count = {}
for cmp in data:
    if cmp in number_count:
        number_count[cmp] += 1
        continue
    number_count[cmp] = 1

for i in range(N):
    C = 0
    number_count_temp = number_count.copy()
    number_count_temp[str(data[i])] -= 1
    for cmp in number_count_temp:
        C += int(number_count_temp[cmp] * (number_count_temp[cmp] - 1) / 2)

    print(str(C))


### FIXED CODE ###

N = int(input())
data = [i for i in input().split()]

number_count = {}
for cmp in data:
    if cmp in number_count:
        number_count[cmp] += 1
        continue
    number_count[cmp] = 1

C_tot = 0
for cmp in number_count:
    C_tot += int(number_count[cmp] * (number_count[cmp] - 1) / 2)

for k in range(N):
    C = C_tot - int(number_count[data[k]] * (number_count[data[k]] - 1) / 2) + int((number_count[data[k]] - 1) * (number_count[data[k]] - 2) / 2)
    print(str(C))
### BUGGY CODE ###

n = int(input())
num = [0 for i in range(n)]
for i in range(n):
    num[i] = int(input())
m = -float('inf')
res = m
for i in range(n):
    for j in range(i+1,n):
        if m < num[j] - num[i]:
            m = num[j] - num[i]
        res = max(m,res)
print(res)

### FIXED CODE ###

import sys
input()
mx = -float('inf')
res = mx
mn = int(input())
for i in map(int,sys.stdin.readlines()):
        if mx < i - mn:
            mx = i - mn
        if 0 > i - mn:
            mn = i
        res = max(mx,res)
print(res)
### BUGGY CODE ###

def ismof9(n):
    s = 0
    while n:
        r = n % 10
        s += r
        n //= 10
    if s % 9 == 0:
        return "Yes"
    else:
        return "No"


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

main()


### FIXED CODE ###

def ismof9(n):
    _str = str(n)
    _sum = 0
    for ch in _str:
        _sum += int(ch)
    if _sum % 9 == 0:
        return "Yes"
    else:
        return "No"


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

main()
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            for l in range(ma-k):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(ma-k):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(ma-k):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]

for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = input()
l = []
r = []
cnt = []
for i in range(q):
    _l,_r = [int(i) for i in input().split()]
    l.append(_l)
    r.append(_r)
for i in range(q):
    cnt.append(s[l[i]-1:r[i]].count('AC'))
for i in range(len(cnt)):
    print(cnt[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = input()
t = [0] * (n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x[:]
#      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
### BUGGY CODE ###

n,k = map(int,input().split())
list = list(map(int,input().split()))
 
aaa = 0
i = 0
while i < n-k+1:
    a = sum(list[i:i+k])
    if aaa <= a:
        aaa = a
    i += 1 
 

 
print((aaa+k)/2) 

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
 
aaa = sum(L[0:k])
ans = aaa
for i in range(k,n):
    aaa += L[i]
    aaa -= L[i-k]
    if ans <= aaa:
        ans = aaa
    i += 1    
     
print((ans+k)/2)
### BUGGY CODE ###

from collections import deque
import sys

H, W = map(int, sys.stdin.readline().strip().split())
grid = [list(sys.stdin.readline().strip()) for _ in range(H)]
dq = deque([(0, 0, 1)])
nexts = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
    h, w, cnt = dq.popleft()
    grid[h][w] = cnt
    for y, x in nexts:
        if 0 <= y + h and y + h < H and 0 <= x + w and x + w < W and grid[y + h][x + w] == '.':
            dq.append((y + h, x + w, cnt + 1))
            
sharp_num = 0
max_num = 0
for h in range(H):
    sharp_num += grid[h].count('#')
if grid[-1][-1] == '.' or grid[-1][-1] == '#':
    print(-1)
else:
    print(H * W - grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

from itertools import product

N=int(input())
S=input()
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0

for com in u:
  x_flag=False
  y_flag=False
  x=com[0]
  y=com[1]
  z=com[2]
    
  for i in range(N):
    if S[i]==x:
      x_flag=True
      break
  if x_flag:
    for j in range(i+1,N):
      if S[j]==y:
        y_flag=True
        break
  if y_flag:
    for k in range(j+1,N):
      if S[k]==z:
        ans+=1
        break
        
print(ans)


### FIXED CODE ###

from itertools import product

N=int(input())
S=list(input())
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0
for com in u:
  x=com[0]
  y=com[1]
  z=com[2]
  
  if x in set(S):
    idx_x = S.index(x)
    tmp1 = S[idx_x+1:]
    if y in set(tmp1):
      idx_y = tmp1.index(y)
      tmp2 = tmp1[idx_y+1:]
      if z in set(tmp2):
        ans+=1
        continue
        
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7

def p(n,r):
    if n<r:
        return 0
    re=1
    for i in range(n-r+1,n+1):
        re*=i
        re%=mod
    return re
ans=k
q=[0]
v=[0]*n
v[0]=1
while len(q)>0:
    s=q.pop(0)
    c=0
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            c+=1
            q.append(es)
    if s==0:
        ans*=p(k-1,c)
        ans%=mod
    else:
        ans*=p(k-2,c)
        ans%=mod
print(ans%mod)


### FIXED CODE ###

from collections import deque
n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
ans=k
q=deque([0])
v=[0]*n
v[0]=1
vc=1
while q and vc<n:
    s=q.popleft()
    c=0
    if s==0:
        kai=k-1
    else:
        kai=k-2
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            vc+=1
            c+=1
            q.append(es)
            ans*=kai
            ans%=mod
            kai-=1
print(ans%mod)
### BUGGY CODE ###

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

ans_sum = 0

for i in range(n):
    count = a_li.count(i + 1)
    count = count*(count - 1) // 2
    ans_sum += count

for a in a_li:
    count = a_li.count(a)
    if count == 1:
        print(ans_sum)
    else:
        print(ans_sum - count*(count - 1) // 2 + (count - 1)*(count - 2) // 2)

### FIXED CODE ###

from collections import Counter

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

ans_sum = 0

counter = Counter(a_li)

for i in counter.values():
    ans_sum += i*(i - 1) // 2

for a in a_li:
    count = counter[a]
    if count == 1:
        print(ans_sum)
    else:
        print(ans_sum - count*(count - 1) // 2 + (count - 1)*(count - 2) // 2)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
D=[]
def factorization(N):
    temp={}
    while True:
        divided=False
        for i in range(2, int(N**0.5)+1):
            if N%i==0:
                if i in temp:
                    temp[i]+=1
                else:
                    temp[i]=1
                N=N//i
                divided=True
                break
        if not divided:
            if N in temp:
                temp[N]+=1
            else:
                temp[N]=1
            break
    return temp
G={}
for a in A:
    b=factorization(a)
    D.append(b)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
cnt=0
for i in range(len(A)):
    x=1
    b=D[i]
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
        x%=P
    ans+=x
    ans%=P
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a>b:
        return gcd(b,a)
    if a==0:
        return b
    return gcd(b-a*(b//a),a)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
s=1
for a in A:
    s=lcm(s,a)
ans=0
for a in A:
    ans+=s//a
print(ans%(10**9+7))
### BUGGY CODE ###

n = int(input())

G = [1]
while True:
	g = G[-1] * 2 + 1
	if g > n:
		break
	G.append(g)
G.reverse()

A = [int(input()) for _ in range(n)]
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt, *A, sep='\n')


### FIXED CODE ###

import sys

n = int(input())
if n == 1:
	G = [1]
else:
	G = [g for g in [1, 4, 10, 23, 57, 132, 301, 701] if g < n]
	while True:
		g = int(2.25 * G[-1])
		if g > n:
			break
		G.append(g)
	G.reverse()

A = list(map(int, sys.stdin))
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j -= g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt)
for a in A:
	print(a)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
for i in range(N):
    A2 = A.copy()
    A2.pop(i)
    print(max(A2))
    

### FIXED CODE ###

import sys
def main():
    N = int(sys.stdin.readline())
    A = [int(sys.stdin.readline()) for i in range(N)]
    maxa = max(A)
    maxb = sorted(A)[-2]
    if A.count(maxa) > 1:
        for i in range(N):
            print(maxa)
    else:
        for i in range(N):
            if A[i] != maxa:
                print(maxa)
            else:
                print(maxb)
                
main()
### BUGGY CODE ###

import itertools

n, m, x = map(int, input().split())
L = list(list(map(int, input().split())) for _ in range(n))
ans = float('inf')
p = []
for i in range(1, n + 1):
    for j in itertools.permutations(L, i):
        p.append(list(j))

for k in p:
    s = [0] * (m + 1)
    for l in range(len(k)):
        for t in range(m + 1):
            s[t] += k[l][t]
            
    sum_price = 0
    for i in range(1, m + 1):
        if s[i] < x:
            sum_price = float('inf')
            break
        sum_price = s[0]
    if sum_price < ans:
        ans = sum_price

if ans == float('inf'):
    print('-1')
else:
    print(ans)


### FIXED CODE ###

def solve(L):
    cost = 0
    s = [0] * m
    for k in range(n):
        if L[k] == 1:
            cost += A[k][0]
            for l in range(1, m+1):
                s[l-1] += A[k][l]
    if all(s[i] >= x for i in range(m)):
        return cost
    else:
        return float('inf')

n, m, x = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
for i in range(2 ** n):
    L = [0] * n
    for j in range(n):
        if ((i >> j) & 1) != 0:
            L[j] = 1
    ans = min(ans, solve(L))
if ans == float('inf'):
    print(-1)
else:
    print(ans)