Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, graph, s, yen=True):
    dist = [10**18] * n
    queue = [(s, 0)]
    dist[s] = 0
    while queue:
        v, d = heapq.heappop(queue)
        if dist[v] < d:
            continue
        for child, costa, costb in graph[v]:
            if yen:
                cost = costa
            else:
                cost = costb
            if dist[v] + cost < dist[child]:
                dist[child] = dist[v] + cost
                heapq.heappush(queue, (child, dist[child]))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    s_graph = [[] for _ in range(n)]
    t_graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        s_graph[u].append((v, a, b))
        s_graph[v].append((u, a, b))
        t_graph[u].append((v, a, b))
        t_graph[v].append((u, a, b))
    s_dist = dijkstra(n, s_graph, s, True)
    t_dist = dijkstra(n, t_graph, t, False)

    cost = 10 ** 18
    ans = []
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans.append(10 ** 15 - cost)
    for x in reversed(ans):
        pritn(x)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(n, s, g, mode):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for w, *a in g[v]:
            nd = d + a[mode]
            if dist[w] > nd:
                dist[w] = nd
                heappush(hq, (nd, w))
    return dist

def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    graph = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    s_dist = dijkstra(n, s, graph, 0)
    t_dist = dijkstra(n, t, graph, 1)

    cost = float("inf")
    ans = [0] * n
    for i in range(n-1, -1, -1):
        cost = min(cost, s_dist[i] + t_dist[i])
        ans[i] = 10 ** 15 - cost
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()
# ABC124 D - Handstand
from math import ceil
n,k=map(int,input().split())
s=input()

l=[]
tmp=''
t_cnt=0
for i,ss in enumerate(s):
    if i==0:
        tmp=ss
        t_cnt+=1
        if len(s)==1:
            l.append(t_cnt)
            break
        continue
    if i==n-1:
        if ss==tmp:
            t_cnt+=1
            l.append(t_cnt)
        else:
            t_cnt=1
            l.append(t_cnt)
        continue
    if ss==tmp:
        t_cnt+=1
    else:
        l.append(t_cnt)
        t_cnt=1
        tmp=ss

# print(l)
l+=[0]
ans=0
if s[0]=='0':
    for i in range(0,ceil(n/2),2):
        if i==0:
            ans=sum(l[:2*k-1])
            continue
        ans=max(ans,ans+l[i+1]-l[i-1])
else:
    for i in range(1,ceil(n/2)+1,2):
        if i==1:
            ans=sum(l[:2*k+1])
            continue
        ans=max(ans,ans+l[i+1]-l[i-1])
    
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
l=[]
if s[0]=="0":
  l.append(0)

from itertools import groupby,accumulate
gr=groupby(s)

for K,g in gr:
  l.append(len(list(g)))

l_sum=list(accumulate(l))
l_sum=[0]+l_sum

add=2*k+1
ans=0
for i in range(0,len(l)+1,2):
  left=i
  right=min(i+add,len(l))
  tmp=l_sum[right]-l_sum[left]
  ans=max(tmp,ans)
print(ans)
x = int(input())

lis = [100, 101, 102, 103, 104, 105]

if x < 100:
    print(0)
else:
    c = x//100
    for i in range(1<<c):
        tmp = 0
        for j in range(c):
            if ((i >> j) & 1):
                tmp += lis[j]
        if tmp == x:
            print(1)
            exit()
print(0)

### FIXED CODE ###

x = int(input())

flag = 0
if x >= 2000:
    print(1)
    exit()
else:
    for i in range(20):
        for j in range(20):
            for k in range(20):
                for l in range(20):
                    for m in range(20):
                        for n in range(20):
                            if i*100+j*101+k*102+l*103+m*104+n*105 == x:
                                flag = 1
                                print(1)
                                exit()
if flag != 1:
    print(0)
import sys
input = sys.stdin.readline

D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
t=[int(input()) for i in range(D)]

for i in range(D):
    print(13)

### FIXED CODE ###

import sys
input = sys.stdin.readline

D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
#t=[int(input()) for i in range(D)]

for i in range(D):
    print(13)
import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect
import numpy as np

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
m = np.cumsum(l)
p = m[-1]

maximum_operation = [0] * N

ll = []
for x in range(1, N+1):
    a = bi.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = m[a-1] 
    ll.append((b + c)/x)
ll.sort()

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
import bisect
N, K = map(int, input().split())
A = list(map(int, input().split()))
index = [-1]*(10**5*2+10)
last = [-1]*(N+1)
for i in range(N)[::-1]:
    ind = index[A[i]]
    if ind>=0:
        last[i] = last[ind+1]
        index[A[i]] = -1
    else:
        last[i] = A[i]
        index[A[i]] = i
first_index = [-1]*(10**5*2+10)
for i in range(N):
    if first_index[A[i]]<0:
        first_index[A[i]] = i
loop = [0]
ind = 0
while True:
    next_index = first_index[last[ind]]+1
    if next_index == N or next_index == 0:
        break
    loop.append(next_index)
    ind = next_index
ll = len(loop)
index = [[] for _ in range(10**5+10)]
ans = []
for i in range(loop[K%ll-1], N):
    index[A[i]].append(i)
i=loop[K%ll-1]
while i<N:
    if index[A[i]][-1]==i:
        ans.append((str(A[i])))
        i+=1
    else:
        i=index[A[i]][bisect.bisect_left(index[A[i]], i)+1]+1
print(' '.join(ans))

### FIXED CODE ###

from bisect import bisect_right
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
a_to_i = [[] for _ in range(max(A)+1)]
for i in range(N):
    a_to_i[A[i]].append(i)
next_index = [-1]*N
for i in range(N):
    a = A[i]
    j = bisect_right(a_to_i[a], i)
    if j == len(a_to_i[a]):
        next_index[i] = a_to_i[a][0]+N
    else: next_index[i] = a_to_i[a][j]
now = 0
cnt = 0
while True:
    i = next_index[now]
    if i>=N:
        i%=N
        cnt+=1
    else: now = i
    i+=1
    if i>=N:
        cnt+=1
        i%=N
    now = i
    if now == 0:
        break
K%=cnt
if K==0:
    print()
    sys.exit()
ans = [A[0]]
K*=N
K-=1
now = 0
while now<K:
    ni = next_index[now%N]+1
    if(now//N)*N+ni-1 == K:
        ans.pop()
        break
    if (now//N)*N+ni>K:
        now+=1
        ans.append(A[now%N])
    else:
        now = (now//N)*N+ni
        ans[-1] = A[now%N]




print(*ans, sep = ' ')
N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    x, y = map(int, input().split())
    union(x,y)
    
cnt = [0] * (N+1)

for i in range(1,N+1):
    z = find(i)
    cnt[z] += 1

print(max(cnt))



### FIXED CODE ###

from collections import Counter 

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

for _ in range(M):
    x, y = map(int, input().split())
    uf1.union(x-1,y-1)

for i in range(N):
    uf1.find(i) 
c = list(Counter(uf1.par).values())
print(max(c))
a=int(input())
b=int(input())
print(a*b)

### FIXED CODE ###

A,B=map(int,input().split())
print(A*B)
A, B = [int(i) for i in input().split())]
ret = A - B*2
print(ret if ret > 0 else 0)


### FIXED CODE ###

A, B = [int(i) for i in input().split()]
ret = A - B*2
print(ret if ret > 0 else 0)
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(2*10**6)
f_mod_inverse=[1]*(2*10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

### FIXED CODE ###

MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(3*10**6)
f_mod_inverse=[1]*(3*10**6)
for i in range(1,3*10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)
from math import *
while True:
    n = int(raw_input())
    if n == 0 :
        break
    for i in range(n):
        sco = map(int,raw_input().split())
        ave=0.0
        for i in sco:
            ave += i
        ave /= n

        dev = 0.0
        for i in sco:
            dev += (i-ave)*(i-ave)
        dev /= n

        print sqrt(dev)

### FIXED CODE ###

from math import *
while True:
    n = 0
    n = int(input())
    if n == 0:
        break
    else :
        sco = map(int,raw_input().split())
        for i in range(n):
            ave=0.0
            for i in sco:
                ave += i
            ave /= n
            dev = 0.0
            for i in sco:
                dev += (i-ave)*(i-ave)
            dev /= n
        print sqrt(dev)
n=int(input())
s=[input() for _ in range(n)]

lis=[collections.Counter(list(s[i])) for i in range(n)]
cnt=0
for i in range(n):
    for j in range(i+1,n):
        if lis[i].items()==lis[j].items(): cnt+=1
print(cnt)

### FIXED CODE ###

import collections

n=int(input())
s=[(input()) for _ in range(n)]

lis=[list(s[i]) for i in range(n)]
lis_sort = [sorted(lis[i]) for i in range(n)]
lis_sort = [''.join(lis_sort[i]) for i in range(n)]
lis_sort.sort()

c = collections.Counter(lis_sort)
values, counts = zip(*c.most_common(len(c)))
cnt=0
for i in range(len(counts)):
    if counts[i]==2: cnt+=1
    elif counts[i]>2: cnt+=counts[i]*(counts[i]-1)//2
print(cnt)
import math
n = int(input())
 
print(math.factorial(n) // math.factorial(n - 3))

### FIXED CODE ###

N = int(input())
print(N*N*N)
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N,K = LI()
    a = LI()
    if max(a) < K:
        return 'IMPOSSIBLE'
    if K in a:
        return 'POSSIBLE'
    t = a[0]
    for c in a[1:]:
        t = math.gcd(c, t)
    if t <= 1:
        return 'POSSIBLE'
    for c in a:
        if (c > K) and (((c-K) % t) == 0):
            return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N,K = LI()
    a = LI()
    if max(a) < K:
        return 'IMPOSSIBLE'
    if K in a:
        return 'POSSIBLE'
    t = a[0]
    for c in a[1:]:
        t = gcd(c, t)
        if t <= 1:
            return 'POSSIBLE'
    for c in a:
        if (c > K) and (((c-K) % t) == 0):
            return 'POSSIBLE'

    return 'IMPOSSIBLE'


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

#print(N,M)

num=[]
answer=[]
correct=[False] * N
correctCount = 0
wrongCount = 0
wrong=[0] * N
for k in range(M):
    n,a=input().split()
    num.append(int(n))
    answer.append(a)
    if a == "AC":
        if correct[n] == False:
            correct[n] = True
            correctCount += 1
            wrongCount += wrong[n]
    else:
        if correct[n] == False:
            wrong[n] += 1



    
#print(num)
#print(answer)
    
'''
preCorrect = False
correctCount=0
wrongCount = 0
temp_wrongCount = 0


for i in range(M):
    if i > 0 and num[i] != num[i-1]:
        if preCorrect == True:
            preCorrect = False
            temp_wrongCount = 0
        else:
            temp_wrongCount = 0
    
    
    if preCorrect == True:
        continue

    if answer[i] == "AC":
        correctCount += 1
        preCorrect = True
        wrongCount += temp_wrongCount
    if answer[i] == "WA":
        temp_wrongCount += 1
'''
print(correctCount, wrongCount)
    




### FIXED CODE ###

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

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])
N = int(input())
W = [int(i) for i in input().split()] 
onon = 0
hoge = sum(W)
for i in range(N):
    onon += W[0]:
    hoge -= W[0]:
    result = abs(onon - hoge)
    if result <= nowresult:
        nowresult = result
print(nowresult)


### FIXED CODE ###

N = int(input())
W = [int(i) for i in input().split()] 
onon = 0
hoge = sum(W)
nowresult = sum(W)
for i in range(N):
    onon += W[i]
    hoge -= W[i]
    result = abs(onon - hoge)
    if result <= nowresult:
        nowresult = result
print(nowresult)
def LI():
	return [ int(s) for s in input().split() ]
N,M = LI()
A = LI()

print('Yes') if sum(map(lambda x: x >= (1/4/M))) >= M else print('No')



### FIXED CODE ###

def LI():
	return [ int(s) for s in input().split() ]
N,M = LI()
A = LI()
sum_A = sum(A)
 
print('Yes') if sum(map(lambda x: x >= sum_A*(1/4/M), A)) >= M else print('No')
import itertools

import numpy as np

H, W, M = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(M)]
F = np.zeros([H, W], dtype=np.int64)

for h, w in HW:
    F[h - 1, w - 1] = 1

# 各方向の和を計算
A = np.sum(F, axis=0)
B = np.sum(F, axis=1)

maxA = np.max(A)
maxB = np.max(B)

# 最大値を取るindex
ind_A = np.arange(W)[A == maxA]
ind_B = np.arange(H)[B == maxB]

cnt = 0
ans = maxA + maxB
"""
for h, w in itertools.product(ind_B, ind_A):
    if F[h, w] == 0:
        break

    cnt += 1
    if cnt == M:
        ans -= 1
        break
else:
    ans -= 1
"""
print(ans)


### FIXED CODE ###

import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()
list_sunuke = []
list_m = []

for i in range(5):
    list_sunuke.append(input())

for i in range(5):
    list_m.append(i+1)

for i in range(5):
    if list_sunuke[i] != list_m[i]:
        print(list_m[i])
        break

### FIXED CODE ###

list_sunuke = input().split()
list_m = []

for i in range(5):
    list_m.append(i+1)

for i in range(5):
    if int(list_sunuke[i]) != list_m[i]:
        print(list_m[i])
n,m = map(int,input().split())

l=list(input().split() for _ in range(m))

w=[0]*n
a=[0]*n
seitou=0
pena=0

for i in l:
    k=int(i[0])-1
    if a[k]==0:
        if i[1]=="AC":
            a[k]+=1
        else:
            w[k]+=1

seitou=sum(a)
for j in range(n):
    if a[i]==1:
        pena+=w[i]
        
print(seitou,pena)

### FIXED CODE ###

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

l=list(input().split() for _ in range(m))

w=[0]*n
a=[0]*n
seitou=0
pena=0

for i in l:
    k=int(i[0])-1
    if a[k]==0:
        if i[1]=="AC":
            a[k]+=1
        else:
            w[k]+=1

seitou=sum(a)
for j in range(n):
    if int(a[j])==1:
        pena+=w[j]
        
print(seitou,pena)
import sys

n,k=map(int,input().split())
s=input()

lcnt=-1
rcnt=-1

rr=[0]*n
ll=[0]*n
sim=""
for si in s:
    if si=="R" and sim=="R":
        rr[rcnt]+=1
    elif si=="R" and sim!="R":
        rcnt+=1
        rr[rcnt]=1
    if si=="L" and sim=="L":
        ll[lcnt]+=1
    elif si=="L" and sim!="L":
        lcnt+=1
        ll[lcnt]=1
    sim=si
        

ll=[i for i in ll if i!=0]
rr=[i for i in rr if i!=0]
#print(ll)
#print(rr)

maxlen=max(len(ll),len(rr))
if maxlen<=k:
    print(n-1)
    sys.exit()
    
for i in range(k):
    ll[i]+=rr[i]
    rr[i]=0

for i in range(maxlen-1):
    if ll[i]!=0 and rr[i]==0 :
        ll[i+1]+=ll[i]
        ll[i]=0

icnt=0
for i in range(len(ll)):
    icnt+=max(ll[i]-1,0)
for i in range(len(rr)):
    icnt+=max(rr[i]-1,0)
    
print(icnt)


### FIXED CODE ###

import sys

n,k=map(int,input().split())
s=input()

lcnt=-1
rcnt=-1

rr=[0]*n
ll=[0]*n
sim=""
for si in s:
    if si=="R" and sim=="R":
        rr[rcnt]+=1
    elif si=="R" and sim!="R":
        rcnt+=1
        rr[rcnt]=1
    if si=="L" and sim=="L":
        ll[lcnt]+=1
    elif si=="L" and sim!="L":
        lcnt+=1
        ll[lcnt]=1
    sim=si
        
ll=[i for i in ll if i!=0]
rr=[i for i in rr if i!=0]
#print(ll)
#print(rr)

minlen=min(len(ll),len(rr))
if minlen<=k:
    print(n-1)
    sys.exit()
    
for i in range(k):
    ll[i]+=rr[i]
    rr[i]=0

for i in range(len(ll)-1):
    if i<len(rr) and ll[i]!=0 and rr[i]==0 :
        ll[i+1]+=ll[i]
        ll[i]=0

icnt=0
for i in range(len(ll)):
    icnt+=max(ll[i]-1,0)
for i in range(len(rr)):
    icnt+=max(rr[i]-1,0)
    
print(icnt)
import sys
input = sys.stdin.readline


def main():
    n, m, x = map(int, input().split())
    lst = [[int(i) for i in input().split()] for _ in range(n)]

    ans = []
    for i in range(1 << n):
        understand = []
        money = 0
        for j in range(n):
            if (i >> j) & 1 == 0:
                continue
            money += lst[0]
            for k in range(m):
                understand[k] += lst[k + 1]
        if all([i >= x for i in understand]):
            ans.append(money)

    print(min(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
n, m, x = map(int, input().split())
lst = []

for i in range(n):
    lst.append([int(i) for i in input().split()])

ans_list = []

for i in range(1, n + 1):
    for j in itertools.combinations(lst, i):
        under_list = [0] * m
        money = 0
        for k in j:
            money += k[0]
            for i in range(m):
                under_list[i] += k[i + 1]
        if all([i >= x for i in under_list]):
            ans_list.append(money)

if not ans_list:
    ans = -1
else:
    ans = min(ans_list)

print(ans)
A = list(map(int, input().split()))

B = A.sort(reverse=True)

print(B[0] - B[2])

### FIXED CODE ###

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

A.sort(reverse=True)

print(A[0]-A[2])
N, M = map(int, input().split())
a = int(input())
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  a = int(input())
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
try:
  a = int(input())
except EOFError:
  a = 0
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  try:
    a = int(input())
  except EOFError:
    pass
    
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)
n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = []
wa_dict = {}
num_wa = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC':
        ac_list.append(p)
        num_wa += wa_dict[p]
    elif p not in ac_list:
        if p not in wa_dict.keys():
            wa_dict[p] = 1
        else:
            wa_dict[p] += 1
         
print(num_ac, num_wa)

### FIXED CODE ###

n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = []
wa_list = [0 for i in range(n)]
num_wa = 0
num_ac = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC' and wa_list[p-1] != -1:
        ac_list.append(p)
        num_wa += wa_list[p-1]
        num_ac += 1
        wa_list[p-1] = -1
    elif wa_list[p-1] != -1:
        wa_list[p-1] += 1
        
print(num_ac, num_wa)