Harryxun/stf_run huggingface dataset:
from itertools import product

n, m, x = map(int, input().split())
c = [0] * n
a = [0] * n
for i in range(n):
    inp = [int(_) for _ in input().split()]
    c[i] = inp[0]
    a[i] = inp[1:]

#print(c)
#print(a)

ans = 10**10
pat = list(product([0, 1], repeat=n))

for p in pat:
    a_val = [0] * n
    c_yen = 0

    for i in range(n):
        if p[i] == 1:
            c_yen += c[i]
            for j in range(m):
                a_val[j] += a[i][j]

    flag = True
    for i in range(m):
        if a_val[i] < x:
            flag = False
            break
    if flag:
        ans = min(ans, c_yen)

if ans == 10**10:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n, m, x = map(int, input().split())
c = [0] * n
for i in range(n):
    c[i] = [int(_) for _ in input().split()]

ans = 10**10
for i in range(2 ** n):
    state = [0] * n
    for j in range(n):
        state[j] = (i >> j) & 1
    #print(state)
    num = [0] * m
    val = 0

    for j in range(n):
        if state[j] == 1:
            for k in range(m):
                num[k] += c[j][k+1]
            val += c[j][0]

    flag = True
    for j in range(m):
        if num[j] < x:
            flag = False
            break
    if flag:
        ans = min(ans, val)

if ans == 10**10:
    print(-1)
else:
    print(ans)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans

### FIXED CODE ###

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

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)
from heapq import heappush, heappop

N, K = map(int, input().split())
h = []
for i in range(N):
  t, d = map(int, input().split())
  heappush(h, (-d, t))

# initial
res = 0
sum = 0
q = []
used = {}
for i in range(K):
  (d, t) = heappop(h)
  if t not in used:
    used[t] = 1
  else:
    heappush(q, (-d, t))
  sum += -d
res = len(used)*len(used)+sum

# swap minimum
while q:
  (d, t) = heappop(h)
  if t not in used:
    used[t] = 1
    m, _ = heappop(q)
    sum = sum - m - d
  res = max(res, len(used)*len(used) + sum)
  
print(res)

### FIXED CODE ###

from heapq import heappush, heappop

N, K = map(int, input().split())
h = []
for i in range(N):
  t, d = map(int, input().split())
  heappush(h, (-d, t))

# initial
res = 0
sum = 0
q = []
used = {}
for i in range(K):
  (d, t) = heappop(h)
  if t not in used:
    used[t] = 1
  else:
    heappush(q, (-d, t))
  sum += -d
res = len(used)*len(used)+sum

# swap minimum
while q and h:
  (d, t) = heappop(h)
  if t not in used:
    used[t] = 1
    m, _ = heappop(q)
    sum = sum - m - d
  res = max(res, len(used)*len(used) + sum)
  
print(res)
nk = [int(x) for x in input().split(' ')]

def abs_diff(n, k):
  first_time = abs(n - k)
  second_time = abs(first_time - k)
  if second_time < first_time:
    abs_diff(first_time, k)
  elif first_time < n:
    print(first_time)
  else:
    print(n)

abs_diff(nk[0], nk[1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
 
print(min(n % k, abs(k - n % k)))
N = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

arrival = 1
ans = 0

while arrival < N:
    score = a.popleft()
    if arrival == 1:
        ans += score
        arrival += 1
    else:
        ans += score*min(2, N - arrival)
        arrival += 2

print(ans)

### FIXED CODE ###

from collections import deque

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

A.sort(reverse=True)

a = deque(A)

arrival = 1
ans = 0

while arrival < N:
    score = a.popleft()
    if arrival == 1:
        ans += score
        arrival += 1
    else:
        ans += score*min(2, N - arrival)
        arrival += 2

print(ans)
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}

havew = {}
for _ in range(m):
    h,w = map(lambda x: int(x)-1,input().split())
    if h in dich:
        dich[h] += 1
    else:
        dich[h] = 1
        havew[h] = [False] * worigin
    havew[h][w] = True
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1

dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])

# print(havew)
#
# print(dichi)
# print(dicwi)

hmax = dichi[0][1]
wmax = dicwi[0][1]

for hs in dichi:
    if hs[1] != hmax:
        break
    for ws in dicwi:
        # print(hs, ws)
        if ws[1] != wmax:
            break
        if not havew[hs[0]][ws[0]]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)



### FIXED CODE ###

import bisect
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    wlis = sorted(havew[hs[0]])
    for ws in dicwi:
        if ws[1] != wmax:
            break
        idx = bisect.bisect_left(wlis, ws[0])
        if idx >= len(wlis):
            print(hmax+wmax)
            exit()
        if ws[0] != wlis[idx]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)
a = int(input()) * 500
b = int(input())
if a>=b:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

a,b = map(int,input().split())
c = a*500
if c>=b:
  print("Yes")
else:
  print("No")
from collections import deque

h,w=[int(i) for i in input().split() ]

graph=[[None for i in range(w+2)] for j in range(h+2)]
wnum=0
for i in range(w+2):
    graph[0][i]=['#',None]
    graph[h+1][i]=['#',None]
for j in range(h+2):
    graph[j][0]=['#',None]
    graph[j][w+1]=['#',None]
for i in range(h):
    a=input()
    for j in range(w):
        if a[j]=='.':
            wnum+=1
        graph[i+1][j+1]=[a[j],None]

q=deque([])
q.append((1,1))
graph[1][1][1]=0
d_min=None
while len(q)!=0:
    x,y=q.popleft()
    for cx,cy in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
        if graph[cx][cy][0]=='.':
            if graph[cx][cy][1]==None:
                graph[cx][cy][1]=graph[x][y][1]+1
                if (cx,cy)==(h,w):
                    d_min=graph[cx][cy][1]
                    break
                q.append((cx,cy))
print(wnum-d_min-1)

### FIXED CODE ###

from collections import deque

h,w=[int(i) for i in input().split() ]

graph=[[None for i in range(w+2)] for j in range(h+2)]
wnum=0
for i in range(w+2):
    graph[0][i]=['#',None]
    graph[h+1][i]=['#',None]
for j in range(h+2):
    graph[j][0]=['#',None]
    graph[j][w+1]=['#',None]
for i in range(h):
    a=input()
    for j in range(w):
        if a[j]=='.':
            wnum+=1
        graph[i+1][j+1]=[a[j],None]

q=deque([])
q.append((1,1))
graph[1][1][1]=0
d_min=None
while len(q)!=0:
    x,y=q.popleft()
    for cx,cy in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
        if graph[cx][cy][0]=='.':
            if graph[cx][cy][1]==None:
                graph[cx][cy][1]=graph[x][y][1]+1
                if (cx,cy)==(h,w):
                    d_min=graph[cx][cy][1]
                    break
                q.append((cx,cy))
if d_min!=None:
   print(wnum-d_min-1)
else:
   print(-1)
import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def C(n, r):
    if r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

olist = [C(N+K-2, N) % mod]

def EE(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(min(k2, N+1)):
        if i % 2 == 1:
            olist[j] = div(olist[j] * k2, k2-j)
        olist[j] = div(olist[j] * (k1+j) , N+k1)
        result = (result + olist[j]) % mod
        if i % 2 == 0 and j != N:
            result = (result + div(olist[j] * (N-j), N+k1-1)) % mod

    if N >= k2:
        if i % 2 == 1:
            olist.append((C(k2, k2) * C(N+k1-1, N-k2) * pow(2, k2)) % mod)
        else:
            if i != 2:
                olist[k2] = div(olist[k2] * (k1+k2), N+k1)
            result = (result + div(olist[k2] * (N-k2), N+k1-1)) % mod
        result = (result + olist[k2]) % mod
    return result

result = []
for i in range(K):
    alist = []
    result.append(str(EE(i+2)))
print("\n".join(result + result[:-1][::-1]))


### FIXED CODE ###

import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

NNN = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

def EN(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(k2+1):
        if N < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod) , cmb_f(N+k1-1, j+k1-1, mod)) , pow(2, j) % mod))% mod
    if i % 2 == 1:
        return result
    for j in range(k2+1):
        if N-1 < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod), cmb_f(N+k1-2, j+k1-1, mod)), pow(2, j) % mod))% mod
    return result

if K == 1:
    print(0)
else:
    result = []
    for i in range(K):
        result.append(str(EN(i+2)))
    print("\n".join(result + result[:-1][::-1]))
K = int(input())
A, B = map(int, input().split())
i = A // K
nK = K
OK = False
if A-B > K:
  print('OK')
else:
  while nK =< B:
    if (nK >= A) and (nK <= B):
      OK = True
      print('OK')
      break
    nK = i * K
    i = i + 1
if OK == False:
  print('NG')

### FIXED CODE ###

K = int(input())
A, B = map(int, input().split())
i = A // K
nK = K
OK = False
if A-B > K:
  print('OK')
else:
  while nK <= B:
    if (nK >= A) and (nK <= B):
      OK = True
      print('OK')
      break
    nK = i * K
    i = i + 1
if OK == False:
  print('NG')
s = [x for x in input()]
for _ in range(3):
  if s[i] == s[i+1]:
    print('Bat')
    break
  else:
    print('Good')



### FIXED CODE ###

s = [x for x in input()]
ans = 'Good'
for i in range(3):
  if s[i] == s[i+1]:
    ans = 'Bad'
    break
print(ans)
#-*- coding: UTF-8 -*-

a = int(input())
s = input()

if a => 3200:
    print(s)

elif:
    print("red")


### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)

else:
    print("red")
N,P = map(int,input().split())
i = round(P**(1/N))
j = 2
res = 1
if N == 1:
  print(P)
  break
elif P == 1|N>=40:
  print(1)
  break
else:
  while P%(j**N)==0:
    P = P//(j**N)
    res *= j
  j += 1
  for f in range(j,i+1,2):
    while P%(f**N) == 0:
      P = P//(f**N)
      res *= f
      
  print(res)
  break

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
A, B, K = map(int, input().split())
cnt = 0

for i in range(100, 0, -1):
  if A%i == 0 and B%i == 0:
    cnt += 1
    if cnt = K:
      print(i)
      exit()

### FIXED CODE ###

A, B, K = map(int, input().split())

def make_div(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors

print(sorted(set(make_div(A))&set(make_div(B)), reverse=True)[K-1])
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort()
ok = max(a)*max(f)
ng = -1

while ok-ng > 1:
    mid = (ok+ng)//2
    t = 0
    for i in range(n):
        t += max(0,a[i]-int(mid/f[i]))
    if t > k:
        ng = mid
    else:
        ok = mid

print(ok)

### FIXED CODE ###

a,b = map(int,input().split())
if a <10 and b < 10:
    print(a*b)
else:
    print(-1)
n = int(input())
l = list(map(int,input().split()))
ans = 1
if n == 1:
  if l[0] == 0:
    print(1)
  else:
    print(0)

elif n == 2:
  if l[0] ==0 and l[1] == 1:
    print(1)
  else:
    print(0)

else:
  if l[0] != 0:
    print(0)
  else:
    a = [0]*n
    for i in range(n):
      a[l[i]] += 1

    if a[0] != 1:
      print(0)
    else:
      for i in range(n-1):
        if a[i]!=0 and a[i+1]!=0:
          ans = ans * (a[i]**a[i+1])
        else:
          break

      print(ans%n = int(input())
l = list(map(int,input().split()))
ans = 1
if n == 1:
  if l[0] == 0:
    print(1)
  else:
    print(0)

elif n == 2:
  if l[0] ==0 and l[1] == 1:
    print(1)
  else:
    print(0)

else:
  if l[0] != 0:
    print(0)
  else:
    a = [0]*n
    for i in range(n):
      a[l[i]] += 1

    if a[0] != 1:
      print(0)
    else:
      for i in range(n-1):
        if a[i]!=0 and a[i+1]!=0:
          ans = ans * (a[i]**a[i+1])
        else:
          break

      print(ans%998244353)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 1
t = 1
if n == 1:
  if l[0] == 0:
    print(1)
  else:
    print(0)
 
elif n == 2:
  if l[0] ==0 and l[1] == 1:
    print(1)
  else:
    print(0)
 
else:
  if l[0] != 0:
    print(0)
  else:
    a = [0]*n
    for i in range(n):
      a[l[i]] += 1
 
    if a[0] != 1:
      print(0)
    else:
      for i in range(n-1):
        if a[i]==0 and a[i+1]!=0:
          t = 0
          
        elif a[i]!=0 and a[i+1]!=0:
          ans = ans * (a[i]**a[i+1])
      if t == 1:
        print(ans%998244353)
      else:
        print(0)
N = int(input())
p1, p2, p5 = 1, 1, 1
for _ in range(N):
    s = int(input())
    if s%10 == 0:
        pass
    elif s%5 == 0:
        p5 *= s
    elif s%2 == 0:
        p2 *= s
    else:
        p1 *= s
print(p1 * (max(p2, p3)))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(int(input()))
sums = sum(S)
if sums % 10 != 0:
    print(sums)
else:
    S.sort()
    for s in S:
        if s % 10 != 0:
            print(sums - s)
            break
    else:
        print(0)
#include <iostream>
#include <queue>

using namespace std;

int main()
{
  int n, m; cin >> n >> m;
  
  priority_queue<int> pq;
  while (n--) {
    int a; cin >> a;
    pq.push(a);
  }
  
  while (m--) {
    pq.push(pq.top()/2);
    pq.pop();
  }
  
  long long ans = 0;
  while (pq.size()) {
    ans += pq.top();
    pq.pop();
  }
  
  cout << ans << endl;
  return 0;
}

### FIXED CODE ###

import queue

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))

q = queue.PriorityQueue()
for k in a:
  q.put(k)
  
for _ in range(m):
  q.put(-(-q.get()//2))
  
ans = 0
for _ in range(n):
  ans += q.get()
  
print(-ans)
import math
from functools import reduce
#入力
N = map(int,input().strip().split(' '))         #モンスタ数
A = list(map(int, input().strip().split(' '))) #それぞれの体力


#最大公約数
print( reduce(lambda x, y: math.gcd(x,y), A) )

### FIXED CODE ###

import fractions as fr
import functools as ft


N = map(int, input().split())
A = list(map(int, input().split())) # "1 2 3"と入力

cal1 = lambda x, y : fr.gcd(x, y)

print(ft.reduce(cal1, A))
import math
A,B,C = map(int,input().split())
if C%math.gcd(A,B) == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

import fractions
A,B,C = map(int,input().split())
if C%fractions.gcd(A,B) == 0:
    print("YES")
else:
    print("NO")
n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
l = []
for i in range(min(n, m)):
  l.append(min(a[i], b[i]))
  l.append(max(a[i], b[i]))

for i in range(min(n, m), max(n, m)):
  if n > m:
    l.append(a[i])
  else:
    l.append(b[i])

total = 0
cnt = 0
for i in range(n+m):
  if total+l[i] > k:
    break
  total += l[i]
  cnt += 1
print(cnt)

### FIXED CODE ###

s = int(input())
print(s + s**2 + s**3)
import sys,math,collections,itertools,bisect
input = sys.stdin.readline

N,K=list(map(int,input().split()))
D = list(map(int,input().split()))
Ds = set([0,1,2,3,4,5,6,7,8,9])-set(D)
can = list(itertools.product(Ds,repeat = 5))
candi = []
for c in can:
    candi.append(1**4*c[0]+10**3*c[1]+10**2*c[2]+10**1*c[3]+c[4])
candi = sorted(candi)
print(candi[bisect.bisect_left(candi,N)])


### FIXED CODE ###

import sys,math,collections,itertools,bisect
input = sys.stdin.readline

N,K=list(map(int,input().split()))
D = list(map(int,input().split()))
Ds = set([0,1,2,3,4,5,6,7,8,9])-set(D)
if 0 in Ds:
    can = list(itertools.product(Ds,repeat = 5))
    candi = []
    for c in can:
        candi.append(10**4*c[0]+10**3*c[1]+10**2*c[2]+10**1*c[3]+c[4])
    candi = sorted(candi)
else:
    Ds = Ds | set([0])
    can = list(itertools.product(Ds,repeat = 5))
    candi = []
    for c in can:
        cs = (10**4*c[0]+10**3*c[1]+10**2*c[2]+10**1*c[3]+c[4])
        s = list(str(cs))
        if '0' in s:
            continue
        else:
            candi.append(cs)
    candi = sorted(candi)
    
print(candi[bisect.bisect_left(candi,N)])
from functools import reduce
from math import gcd

if __name__ == '__main__':
    n = int(input())
    a = [int(s) for s in input().split()]
    print(reduce(gcd, a))


### FIXED CODE ###

from functools import reduce

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


if __name__ == '__main__':
    n = int(input())
    a = [int(s) for s in input().split()]
    print(reduce(gcd, a))
s=input()
N=len(s)
f=s.index("a")
F=0
for i in range(N):
    if s[i]=="z":
        F==i
print(F-f+1)

### FIXED CODE ###

s=input()
N=len(s)
f=s.index("A")
F=0
for i in range(N):
    if s[i]=="Z":
        F=i
print(F-f+1)
a, b, c = (i for i in input().split())

d, e, f = (i for i in input().split())

count = 0
if a==d:
    count+=1
elif d==e:
    count+=1
elif c==f:
    count+=1
print(str(count))


### FIXED CODE ###

S = input()

T = input()
count = 0

s=[]
t=[]
for i in S:
    s.append(i)
for j in T:
    t.append(j)


if s[0]==t[0]:
    count+=1
if s[1]==t[1]:
    count+=1
if s[2]==t[2]:
    count+=1

print(str(count))
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

row = []
col = []
data_e = []
data_s = []
for _ in range(m):
    u,v,a,b = map(int, input().split())
    row.append(u)
    row.append(v)
    col.append(v)
    col.append(u)
    data_e.append(a)
    data_e.append(a)
    data_s.append(b)
    data_s.append(b)

graph_e = csr_matrix((data_e, (row,col)), shape=(n+1, n+1))
graph_s = csr_matrix((data_s, (row,col)), shape=(n+1, n+1))

d_e = dijkstra(csgraph=graph_e, directed=False, indices=s)
d_s = dijkstra(csgraph=graph_s, directed=False, indices=t)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

for i in range(1,n+1):
    print(int(10**15 - ans[i]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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


links_e = [[] for _ in range(n+1)]
links_s = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    links_e[u].append((a,v))
    links_e[v].append((a,u))
    links_s[u].append((b,v))
    links_s[v].append((b,u))

# dijkstra
import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n+1)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

d_e = dijkstra(links_e, s, n)
d_s = dijkstra(links_s, t, n)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

for i in range(1,n+1):
    print(10**15 - ans[i])
%%test_input https://abc108.contest.atcoder.jp/tasks/abc108_c
N, K = map(int, input().split())
ans = sum(((N + a % K) // K)**2 for a in range(1, N + 1) if (2 * a) % K == 0)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = sum(((N + a % K) // K)**2 for a in range(1, N + 1) if (2 * a) % K == 0)
print(ans)
def flip(B, m, n, M, N):
#  print(m,n)
  for mm in range(m-1,m+2):
    for nn in range(n-1,n+2):
      print("mm=", mm, "nn=", nn)
      if 0<=mm and mm<M and 0<=nn and nn<N:
        if B[mm][nn] == 0:
          B[mm][nn] = 1
        else:
          B[mm][nn] = 0
#print(input().split())
MN=list(map(int, input().split()))
B = [[0 for i in range(MN[0])] for j in range(MN[1])]
for m in range(0,MN[0]):
  for n in range(0,MN[1]):
    flip(B, m, n, MN[0], MN[1])
c = 0
for m in range(0,MN[0]):
  for n in range(0,MN[1]):
    c += B[m][n]
#print(B)
print(c)

### FIXED CODE ###

MN=list(map(int, input().split()))
M = MN[0]
N = MN[1]
if N == 1:
  N = MN[0]
  M = MN[1]
if M == 1:
  if N == 1:
    c = 1
  elif N == 2:
    c = 0
  else:
    c = N - 2
else:
  c = (M - 2)*(N - 2)
print(c)
N,A,B = map(int,input().split())
qaws = ""
while(N > len(qaws)):
  qaws += ("B"*A)
  qaws += ("R"*B)
print(qaws[:N].count("B"))

### FIXED CODE ###

n,a,b=map(int,input().split())
ans = n//(a+b)*a
r = n%(a+b)
print(min(r,a)+ans)