Harryxun/stf_run huggingface dataset:
h, w, k=map(int, input(). split())
table=[0]*h

for i in range(h):
    table[i]=input()


cnt=0
ans=0

for i in range(2**h):
    for j in range(2*:w):
        cnt=0
        for k in range(h):
            for l in range(w):
                if ((i>>k)&1)==1 and ((j>>l)&1)==1 and table[k][l]=="#":
                    cnt+=1
        
        if cnt==k:
            ans+=1


print(ans)

### FIXED CODE ###

h, w, k = map(int, input().split())
ans = 0
c = [input() for i in range(h)]
for i in range(1<<h):
    for j in range(1<<w):
        cnt = 0
        for l in range(h):
            for m in range(w):
                if c[l][m] == '#' and (i >> l) & 1 and (j >> m) & 1:
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)
a, b, k = map(int,input().split())
if a < k:
  print(0,(b - k + a), sep=" ")
elif a > k:
  print((a-k),b,sep=" ")
else:
  print(0, 0,sep+" ")

### FIXED CODE ###

a, b, k = map(int,input().split())
if a >= k:
  print(a-k, b)
elif k-a <= b:
  print(0, b-k+a)
else:
  print(0, 0)
S =map(int, input().split(""))
if S = "ABC":
  print("ARC")
else:
  print("ABC")


### FIXED CODE ###

s=input()

if s.find('B')==1:
  print('ARC')
else:
  print('ABC')
import math
a,b = map(int,input().split())
temp = math.gcd(a, b)
ans = a * b // temp
print(ans

### FIXED CODE ###

import math
a,b = map(int,input().split())
temp = math.gcd(a, b)
ans = a * b // temp
print(ans)
n = int(input())
m = 0
for i in range(n):
  a, b = input().split(' ')
  a = int(a)
  if b == 'BTC':
    a = 380000.0*a
  m += a
print(m)

### FIXED CODE ###

n = int(input().rstrip())
m = 0
for i in range(n):
  a, b = input().rstrip().split(' ')
  a = float(a)
  if b == 'BTC':
    a = 380000*a
  m += a
print(m)
n=int(input())
if n<105:
	print(0)
elif 105<=n<135:
	print(1)
elif 135<=n<189:
	print(2)
"""
elif 189<=n:
"""
	print(3)

### FIXED CODE ###

n=int(input())
if n<105:
	print(0)
elif 105<=n<135:
	print(1)
elif 135<=n<165:
	print(2)
elif 165<=n<189:
	print(3)
elif 189<=n<195:
	print(4)
elif 195<=n:
	print(5)
import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
g = [[] for i in range(N)] 
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

plus_list = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    plus_list[p-1] += x

ans = [0] * N
def dfs(v, p):
    ans[v] = plus_list[v] + ans[p]
    for i in range(len(g[v])):
        if g[v][i] != v:
            dfs(x, v)

dfs(0, -1)
print(*ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def dfs(fr, now, num):
    global graph, addsum, ans
    tmp = num + addsum[now]
    for a in graph[now]:
        if a == fr:
            continue
        dfs(now, a, tmp)
    ans[now] = tmp


def main():
    global graph, addsum, ans
    N, Q = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    addsum = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        p -= 1
        addsum[p] += x
    
    ans = [0]*N
    dfs(-1, 0, 0)

    print(*ans)


if __name__ == "__main__":
    main()
import math
N,L = input().split()
N,L = int(N),int(L)
c = math.gcd(6,8)

if(L>=0):
    print(int(0.5*N*(N+1)+N*L-N-(L)))
else:
    n = min([-L,N-1])
    print(int(0.5*N*(N+1)+N*L-N-(L+n)))

### FIXED CODE ###

N,L = input().split()
N,L = int(N),int(L)


if(L>=0):
    print(int(0.5*N*(N+1)+N*L-N-(L)))
else:
    n = min([-L,N-1])
    print(int(0.5*N*(N+1)+N*L-N-(L+n)))
while 1:
    x, y = map(int, raw_input().split())
    if x == 0 and y == 0:
       break
    if y < x:
       print '%s %s' %(y, x)
    else:
       print '%s %s' %(x, y)
    

### FIXED CODE ###

while 1:
   x, y = map(int, raw_input().split())
   if x == 0 and y == 0:
      break
   elif x > y:
      print '%s %s' % (y,x)
   else:
      print '%s %s' % (x,y)
x, n = map(int, input().split())
p = list(map(int, inpot().split()))
for d in range(x + 1):
    for s in [-1, +1]:
        a = x + s * d
        if p.count(a) == 0:
            print(a)
            exit(0)

### FIXED CODE ###

x, n = map(int, input().split())
p = list(map(int, input().split()))
for d in range(x + 1):
    for s in [-1, +1]:
        a = x + s * d
        if p.count(a) == 0:
            print(a)
            exit(0)
import itertools
LR = input().split(' ')
L = int(LR[0])
R = int(LR[1])

min_num = 2000000001
store = [0,0]
num_list = range(L,R+1)
combination_list = list(itertools.combinations(num_list,2))

for comb in combination_list:
    mod = (comb[0] * comb[1] ) % 2019
    if mod < min_num:
        min_num = mod
        store[0] = comb[0]
        store[1] = comb[1]

print(' '.join(map(str,store)))

### FIXED CODE ###

LR = input().split(' ')
L = int(LR[0])
R = int(LR[1])

min_num = 2000000001
flag = False
for l in range(L,R):
    for r in range(l+1,R+1):
        mod = (l*r) %2019
        if mod < min_num:
            min_num = mod
            if mod == 0:
                flag =True
                break
    if flag:
        break

print(min_num)
import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int, input().split()))

  now = 0
  times = 0
  visit =[[0],[0]]

  for _ in range(k):
    times += 1
    now = a[now] - 1
    if now in visit[0]:
      roop = times - visit[1][visit[0].index(now)] #何個の町でループしてるかをroopに代入
      roop_start = visit[1][visit[0].index(now)] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      break
    else:
      visit[0].append(now)
      visit[1].append(times)

  k = (k - roop_start) % roop

  now = 0
  for _ in range(roop_start):
    now = a[now] - 1

  for _ in range(k):
    now = a[now] -1

  print(now+1)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[-1 for _ in range(n)]]
  visit[1][0] = 0
  roop = 0
  roop_start = 0

  for _ in range(k):
    times += 1
    now = a[now] - 1

    if visit[1][now] != -1:
      roop_start = visit[1][now] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      roop = times - roop_start #何個の町でループしてるかをroopに代入
      break
    else:
      visit[0].append(now)
      visit[1][now] = len(visit[0]) - 1

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


if __name__ == '__main__':
  main()
N, M, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())

for i in range(1, N):
    A[i] += A[i-1]
for i in range(1, M):
    B[i] += B[i-1]

A = [0]+A
B = [0]+B
a, b = 0, M
for i in range(N+1):
    k = K-A[i]
    if k < 0:
        break
    while b[j] > k:
        j -= 1
    ans = max(ans, i+j)

print(ans)

### FIXED CODE ###

import bisect
N, M, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
for i in range(1, N):
    A[i] += A[i-1]
for i in range(1, M):
    B[i] += B[i-1]

A = [0]+A
ans = 0
for i in range(N+1):
    b = K-A[i]
    if b < 0:
        break
    j = bisect.bisect_right(B, b)
    if ans < (i+j):
        ans = i+j

print(ans)
import math
n, m = map(int, input().split())

mod = 10 ** 9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+2):
    if m % i == 0:
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n + max(b)+3):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 1
for i in b:
    ans = (ans * nck(n-1+i, n-1)) % mod

print(ans)

### FIXED CODE ###

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

mod = 10**9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+2):
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)
if m > 1:
    b.append(1)

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n + max(b)+3):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 1
for i in b:
    ans *= nck(n-1+i, i)
    ans %= mod

print(ans)
A, B = [int(x) for x in input().split(" ")]

ans = A + B

printf("error" if ans >=10 else ans)

### FIXED CODE ###

A, B = [int(x) for x in input().split(" ")]

ans = A + B

print("error" if ans >= 10 else ans)
n = int(input())
lis = list(map(int, input().split()))

M = max(lis)

for i in range(n):
    if lis[i] == M:
        lis2 = lis[:i] + lis[(i+1):]
        print(max(lis2))
    else:
        print(M)


### FIXED CODE ###

n = int(input())
lis = [int(input()) for _ in range(n)]
lis2 = sorted(lis)
m1 = lis2[-1]
m2 = lis2[-2]

for a in lis:
    if a == m1:
        print(m2)
    else:
        print(m1)
x, y = map(int, input().split())

if (x+y) % 3 != 0:
    ans = 0

else:
    a = (x + y)//3
    b = x-a

    if b <0:
        ans = 0
    else:
        import math 
        val = math.factorial(a)//(math.factorial(b)*math.factorial(a-b))

        ans = val % (10**9+7)

print(int(ans))


### FIXED CODE ###

x, y = map(int, input().split())

from operator import mul
from functools import reduce

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル

if (x+y) % 3 != 0:
    ans = 0

else:
    a = (x + y)//3
    b = x-a

    if x-a <0 or y-a <0:
        ans = 0
    else:
        mod = 10**9+7 #出力の制限
        N = a+b
        g1 = [1, 1] # 元テーブル
        g2 = [1, 1] #逆元テーブル
        inverse = [0, 1] #逆元テーブル計算用テーブル

        for i in range( 2, N + 1 ):
            g1.append( ( g1[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            g2.append( (g2[-1] * inverse[-1]) % mod )

        ans = cmb(a, b, mod)

print(int(ans))
x ** 3

### FIXED CODE ###

x = input()
print(x*x*x)
##
N = int(input())
N_List = list(map(int,input().split()))
Four_List = [i for i in N_List if i % 4 == 0]
Two_List = [i for i in N_List if i % 2 == 0]
if len(Two_List)-len(Four_List) > 0:
    N = N - (len(Two_List) - len(Four_List)) + 1

if N // 2 <= len(Four_List):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N,M = map(int,input().split())
print((N-1)*(M-1))
import numpy as np
k,x = map(int,input().split())

result = np.linspace(x-k+1,x+k-1,k*2-1,dtype = 'int')

for i in range(k*2-1):
    print(str(result[i]),end = " ")

### FIXED CODE ###

import numpy as np
k,x = map(int,input().split())

result = np.arange(x-k+1,x+k,1,dtype = 'int')

for i in range(len(result)):
    print(result[i],end = " ")
def check(N, K):
    if N - 1 == K:
        for i in range(i + 2, N + 1):
            print(1, i)
        return
    elif N - 1 > K:
        
        return
    else:
        print(-1)
        return



if __name__ == "__main__":
    N, K = map(int, input().split())
    check(N, K)


### FIXED CODE ###

def check(N, K):
    if K <= (N - 1)*(N-2) /2:
        k = int((N - 1)*(N-2)/2 - K)
        print(N-1 + k)
        for i in range(2, N+1):
            print(1, i)
        l = 2
        r = 3
        if k != 0:
            for i in range(k):
                if l > N or r > N:
                    break
                print(l, r)
                r+=1
                if r == N+1:
                    l+=1
                    r=l+1
        return
    else:
        print(-1)
        return


if __name__ == "__main__":
    N, K = map(int, input().split())
    check(N, K)
# -*- coding: utf-8 -*-
from functools import reduce
import fractions


def gcd(*numbers):
  return reduce(fractions.gcd, numbers)


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

max_gcd = 0
for i in range(n):
  arr = lst[:i] + lst[i + 1:len(lst)]
  # if min(arr) < max_gcd:
  #   break
  wk_gcd = gcd(*arr)
  max_gcd = wk_gcd if wk_gcd > max_gcd else max_gcd

print(max_gcd)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def check(a, time):
  ret, mod = divmod(time, a)
  value = True if mod == 0 else check(a, ret) if ret > a else False
  return value


a, b, t, biscuit = map(int, input().split() + ["0"])
for i in range(1, t + 1):
  if check(a, i):
    biscuit = biscuit + b

print(biscuit)
#!/usr/bin/python3
import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
sgn = [x // abs(x) for x in a]
M = 10**9 + 7
def modmul(x, y):
    return x * y % M
if reduce(mul, sgn[-k:]) >= 0:
    print(reduce(modmul, a[-k:]))
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in a[:n-k] if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem)) % M)
else:
    print(reduce(modmul, a[:k]))

### FIXED CODE ###

#!/usr/bin/python3
import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
sgn = [0 if x == 0 else x // abs(x) for x in a]
M = 10**9 + 7
def modmul(x, y):
    return x * y % M
if reduce(mul, sgn[-k:]) >= 0:
    print(reduce(modmul, a[-k:], 1))
else:
    largest_unselected_neg = next(i for i, x in enumerate(reversed(a[:-k])) if x < 0) if any(x < 0 for x in a[:-k]) else None
    largest_unselected_pos = next(i for i, x in enumerate(reversed(a[:-k])) if x > 0) if any(x > 0 for x in a[:-k]) else None
    smallest_selected_neg = next(i for i, x in enumerate(a[-k:]) if x < 0) if any(x < 0 for x in a[-k:]) else None
    smallest_selected_pos = next(i for i, x in enumerate(a[-k:]) if x > 0) if any(x > 0 for x in a[-k:]) else None
    can1 = largest_unselected_neg is not None and smallest_selected_pos is not None
    can2 = largest_unselected_pos is not None and smallest_selected_neg is not None
    def ans1():
        return list(reversed(a[:-k]))[largest_unselected_neg] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_pos), 1) % M 
    def ans2():
        return list(reversed(a[:-k]))[largest_unselected_pos] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_neg), 1) % M
    if can1 and not can2:
        print(ans1())
    elif can2 and not can1:
        print(ans2())
    elif can1 and can2:
        if list(reversed(a[:-k]))[largest_unselected_neg] * a[-k:][smallest_selected_neg] > list(reversed(a[:-k]))[largest_unselected_pos] *  a[-k:][smallest_selected_pos]:
            print(ans1())
        else:
            print(ans2())
    else:
        print(reduce(modmul, a[:k], 1))
import numpy as np

hyou = [0]*100001
keisuu = np.array(list(range(0,100001)))

N =  int(input())
a_data = [int(x) for x in input().split()]
Q = int(input())
b_data = [[int(x) for x in input().split()] for _ in range(Q)]

# 数列を分類
for x in a_data:
    hyou[x] += 1
# 操作と合計
for before_value,after_value in b_data:
    # 数値の入れ替え
    hyou[after_value] = hyou[before_value] + hyou[after_value] 
    hyou[before_value] = 0

    # 合計を求めて出力
    hyou_array = np.array(hyou)
    total = np.dot(hyou_array,keisuu)
    print(total)



### FIXED CODE ###

hyou = [0]*100001

N =  int(input())
a_data = [int(x) for x in input().split()]
Q = int(input())
b_data = [[int(x) for x in input().split()] for _ in range(Q)]

# 数列を分類
for x in a_data:
    hyou[x] += 1
# 現段階の合計を求める。
total = 0
for i,x in enumerate(hyou):
    total += i*x

# 操作と合計
for before_value,after_value in b_data:
    total += (after_value - before_value) * hyou[before_value] 
    # 数値の入れ替え
    hyou[after_value] = hyou[before_value] + hyou[after_value] 
    hyou[before_value] = 0

    # 合計を出力
    print(total)
#ABC170 D
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()

if a[0] == a[-1]: # n=1 やサンプル２のような時
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: #１だけは素因数分解するときにバグるので別で処理
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): # 約数のリストつくるやつ
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): #素因数分解
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): # 約数の集合を作る
      c.add(num(div))

# 積集合をとり、それが空でかつ同じ数字が並んでない時に答えを加算
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) #今まで見た数の集合を更新

print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and ((nm < n-2 and a[nm+2] != i) or nm == n-2):
    ans += 1
  s.add(i)

print(ans)
#-*- coding:utf-8 -*-
x = input()
a = input()
b = input()

print((x-a)//b)

### FIXED CODE ###

#-*- coding:utf-8 -*-
x = int(input())
a = int(input())
b = int(input())

print((x-a)-b*((x-a)//b))
import math
x, y = map(int, input().split())
print(math.gcd(x, y))

### FIXED CODE ###

x, y = map(int, input().split())
a = max(x, y)
b = min(x, y)

while a%b != 0:
    temp = a
    a = b
    b = temp%b

print(b)
import statistics
import math
#ABC132 = 2*2*3*11
n = int(input())
d = list(map(int,input().split()))
m = statistics.median(d)
ans = 0
p = 0
q = 0
d.sort()
for i in range(len(d)):
    if d[i]>=m:
        if d[i] == d[i+1]:
            ans += 0
            break
        else:
            p = d[i]
            q = d[i-1]
            break
print(p-q)

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
S = input()
N = int(input())
Q =[]
flag = True
while True:
    try:
        Q.append(list(map(str,input().split())))

    except:
        break;

for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if Q[i][1] == "2" and flag == True:
            S += Q[i][2]#先頭
            
        
        elif Q[i][1] == "2" and flag == False:
            S1 = Q[i][2]+ S
            S = S1
            
        elif Q[i][1] == "1" and flag == True:
            S1 = Q[i][2]+S
            S = S1
            
        elif Q[i][1] == "1" and flag == False:
            S += Q[i][2]

if flag == True:
    print(S)
else:
    print(S[::-1])  

### FIXED CODE ###

N=(input())
if N=="AAA" or N == "BBB":
    print("No")
else:
    print("Yes")
import sys,heapq,time
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u))
    pt -= l*b

sum = 0
while len(blu)>0:
    mv,s,t,b,l,u = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(-mv,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0:
        print(sum+t)
        exit()
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
            #t = b - (m)//l
            #if t==0:
            #    print('6')
            #    exit()
        else:
            m = -m
            t = b + (m+u-1)//u
            #if t==0:
            #    time.sleep(8)
        s = -pt
        heapq.heappush(blu, (-s/t,s,t,b,l,u))


### FIXED CODE ###

import sys,heapq,time
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u,i))
    pt -= l*b

if pt==0:
    print(0)
    exit()

ans = []
reached = False
sum = 0
while len(blu)>0:
    mv,s,t,b,l,u,r = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} s {} t {} b {} l {} u {} pt {} nx {} sum {}".format(-mv,s,t,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        ans.append((s,b,l,u))
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0: # < (u if pt+l*b<0 else l):
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
        sum += t
        break
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
            reached = True
        s = -pt
        ddprint("s/t {} s {} t {}".format(s/t,s,t))
        heapq.heappush(blu, (-s/t,s,t,b,l,u,-1))

sum2 = x * (len(ans)-1)
for z in ans[:-1]:
    s,b,l,u = z
    pt = pt2 - s
    m = pt + l*b
    if m>=0:
        t = (-pt+l-1)//l
    else:
        t = b+(-m+u-1)//u
    if sum2+t < sum:
        sum = sum2+t
print(sum)
b=input()
if "A" = b:
  print("T")
elif b = "T":
  print("A")
elif b = "G":
  print("C")
elif b = "C":
  print("G")

### FIXED CODE ###

b=input()
if "A" == b:
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
elif b == "C":
  print("G")
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

x = []
for i in range(100):
    for j in range(100):
        for k in range(100):
            x.append(A[i] + B[j] + C[k])
x.sort(reverse=True)

for i in range(K):
    print(x[i])
    

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(k,len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])

abc.sort(reverse = True)

for i in range(k):
    print(abc[i])