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

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
    else:
        l[X]=l[Y]
        if r[X]==r[Y]:
            r[Y]+=1

for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

for i in range(N+1):
    l[i]=find(i)
t=[]
for i in range(N+1):
    p=l.count(l[i])-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))


### FIXED CODE ###

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
size=[1]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
        size[X]+=size[Y]
    else:
        l[X]=l[Y]

        if r[X]==r[Y]:
            r[Y]+=1
        if X!=Y:
            size[Y] += size[X]
for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

t=[]
for i in range(N+1):
    p=size[find(i)]-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))
### BUGGY CODE ###

N,W=map(int,input().split())
DP=[[0 for j in range(W+1)]for i in range(N+1)]
for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j>=w:
            DP[i+1][j]=max(DP[i][j-w]+v,DP[i][j])
        else:
            DP[i+1][j]=DP[i][j]
print(DP[N][W])


### FIXED CODE ###

"""
E-Knapsack2
Wが10**9まであるのでdpの置き方を工夫する。
dp[i]:=価値がiのときのナップザックの重さ
"""
N,W = map(int,input().split())
dp = [0]+[W+1]*(N*10**3)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(N*10**3+1-v)[::-1]:
        dp[j+v] = min(dp[j+v],dp[j]+w)
for i in range(N*10**3+1)[::-1]:
    if dp[i]<=W:
        print(i)
        exit()
### BUGGY CODE ###

import math

N, C, K = map(int, input().split())
t_dic = {}
for i in range(N):
    t_num = int(input())
    num = t_dic.get(t_num, 0)
    t_dic[t_num] = num + 1

removed_man_dic = {}
total_car = 0
for key, value in sorted(t_dic.items(), key=lambda x:x[0]):
    limit = key + K
    limit_num = t_dic[key] - removed_man_dic.get(key, 0)
    if limit_num == 0:
        continue
    car_num = int(math.ceil(limit_num / C))
    total_car += car_num
    passenger = C * car_num
    remaining_seat = passenger - limit_num
    removed_man_dic = {}
    for i in range(key + 1, limit + 1):
        num = t_dic.get(i, 0)
        if num <= remaining_seat:
            remaining_seat -= num
            removed_man_dic[i] = num
        else:
            removed_man_dic[i] = remaining_seat
            break

print(total_car)


### FIXED CODE ###

N, C, K = map(int, input().split())
t_sorted = [int(input()) for _ in range(N)]
t_sorted.sort()

car = 0
passenger = 0
target_t, limit = 0, 0
for i, t in enumerate(t_sorted):
    if target_t == 0:
        target_t = t
        limit = t + K
    passenger += 1
    if passenger == C:
        car += 1
        passenger = 0
        target_t = 0
        continue
    if i != N - 1:
        if t_sorted[i + 1] > limit:
            car += 1
            passenger = 0
            target_t = 0
            continue
if passenger > 0:
    car += 1

print(car)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    def add(n, x):
        C[n] = x = C[n] + x
        for c in V[n]:
            V[c].remove(n)
            add(c, x)
    add(0, 0)
    print(' '.join(str(c) for c in C))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0)]
    while cur:
        nxt = []
        for n, x in cur:
            C[n] = x = C[n] + x
            for c in V[n]:
                V[c].remove(n)
                nxt.append((c, x))
        cur = nxt
    print(' '.join(str(c) for c in C))

main()
### BUGGY CODE ###

N,K = map(int, input().split())
a = [int(i) for i in input().split()]
cnt = []
n = 1
while n <= N:
  c = a.count(n)
  if c > 0:
    cnt.append(c)
  n += 1
cnt.sort()
l = len(cnt)
print(sum(cnt[0:(l-K)]))

### FIXED CODE ###

from collections import Counter
N,K = map(int, input().split())
a = [int(i) for i in input().split()]
cnt = Counter(a)
mc = cnt.most_common()
j = 0
ans = 0
while j < len(mc)-K:
  obj = mc[len(mc)-1-j]
  ans += obj[1]
  j += 1
print(ans)
### BUGGY CODE ###

import bisect
import sys


sys.setrecursionlimit(10**6)


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]
    next_robot_list = [-1] * N

    def search_next_robot(r):
        if next_robot_list[r] >= 0:
            return next_robot_list[r]
        if r == N - 1:
            next_robot_list[r] = N
            return N
        if X[r] + D[r] <= X[r + 1]:
            next_robot_list[r] = r + 1
            return r + 1
        next_r_to = bisect.bisect_left(X, X[r] + D[r])
        ret = next_r_to
        for next_r in range(next_r_to - 1, r, -1):
            ret = max(ret, search_next_robot(next_r))
        next_robot_list[r] = ret
        return ret

    for n in range(N - 1, - 1, - 1):
        search_next_robot(n)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        cnt[next_robot_list[n]] += cnt[n]
        cnt[next_robot_list[n]] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import sys


sys.setrecursionlimit(10**6)
INF = 10**6


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [- INF] * (2 * N - 1)

    def update(self, i, x):
        n = self.N + i - 1
        self.data[n] = x
        while n > 0:
            n = (n - 1) // 2
            self.data[n] = max(self.data[2 * n + 1], self.data[2 * n + 2])        

    def elem(self, i):
        return self.data[self.N + i - 1]

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return - INF
        if a <= l and r <= b:
            return self.data[k]
        val_left = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
        val_right = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
        return max(val_left, val_right)

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]

    PW_N = 1
    while PW_N < N:
        PW_N *= 2
    next_robot_tree = SegTree(PW_N)
    next_robot_tree.update(N - 1, N)
    for n in range(N - 2, - 1, - 1):
        if X[n] + D[n] <= X[n + 1]:
            next_robot_tree.update(n, n + 1)
        else:
            next_robot = bisect.bisect_left(X, X[n] + D[n])
            next_robot = next_robot_tree.query(n, next_robot)
            next_robot_tree.update(n, next_robot)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        next_robot = next_robot_tree.elem(n)
        cnt[next_robot] += cnt[n]
        cnt[next_robot] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#abc066d
mod=10**9+7

def com(n,r,m):
 f=[1,1]
 for i in range(2,n+1):
  f.append(f[i-1]*i%m)
 return f[n]*pow(f[r]*f[n-r]%m,m-2,m)%m


N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=com(N+1,k,mod)
 if k-1<=i+j:
  res-=com(i+j,k-1,mod)
 print res%mod


### FIXED CODE ###

#abc066d
mod=10**9+7
fact=[1]*(10**5+2)
for n in range(1,10**5+2):
 fact[n]=n*fact[n-1]%mod

def com(n,k,m):
 return fact[n]*pow(fact[k],m-2,m)*pow(fact[n-k],m-2,m)%m

N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=com(N+1,k,mod)
 if k-1<=i+j:
  res-=com(i+j,k-1,mod)
 print res%mod
### BUGGY CODE ###

def solve():
    p = int(input())
    *A, = map(int, input().split())

    L = p-1
    fact = [1]*(L+1)
    rfact = [1]*(L+1)
    r = 1
    for i in range(1, L+1):
        fact[i] = r = r * i % p
    rfact[L] = r = pow(r, p-2, p)
    for i in range(L, 0, -1):
        rfact[i-1] = r = r * i % p
    V = [(-fact[p-1] * rfact[k] * rfact[p-1-k]) % p for k in range(p)]

    R = [0]*p
    for i, a in enumerate(A):
        if a == 0:
            continue

        b = (-i) % p
        w = 1
        for k in range(p):
            R[k] += V[k] * w % p
            w = w * b % p
        R[-1] += 1
    for i in range(p):
        R[i] %= p
    R.reverse()
    print(*R)
solve()

### FIXED CODE ###

def solve():
    p = int(input())
    *A, = map(int, input().split())
    B = [0]*p

    C = [0]*p
    C[0] = 1
    zeros = [0]*p

    Y = [0]*p
    R = [0]*p
    for i in range(p):
        v = 0
        b = 1
        for j in range(i):
            v += Y[j] * b
            b = b * (i-j) % p
        Y[i] = y = (A[i]-v) * pow(b, p-2, p) % p

        for j in range(i+1):
            R[j] += y * C[j]

        if i < p-1:
            C[1:] = ((b - a*i) % p for a, b in zip(C[1:], C))
            C[0] = 0
    for i in range(p):
        R[i] %= p
    print(*R)
solve()
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 10
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -10
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

from sys import *
from collections import *
from math import *

input = stdin.readline

n = int(input())
arr = list(map(int, input().split()))
mul = 1
for x in arr:
	mul *= x
if mul > 10 ** 18:
	mul = -1
print(mul)

### FIXED CODE ###

from sys import *
from collections import *
from math import *

input = stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
mul = 1
for x in arr:
	mul *= x
	if mul > 10 ** 18:
		print(-1)
		exit(0)
print(mul)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
    for j in range(s+1-i):
        if j>k:break
        z=s-(i+j)
        if 0<=z<=k and s==i+j+z:cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
          cnt+=1
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()

# 1の個数, 0の個数, 1の個数, ..., 1の個数
list10 = []
head = S[0]
cnt = 0

# 左端の1の数
if S[0] == "0":
    list10.append(0)

for i in range(N):
    if S[i] == head:
        cnt += 1
    else:
        list10.append(cnt)
        cnt = 1
        head = S[i]

    if i == N - 1:
        list10.append(cnt)

# 右端の1の数
if S[-1] == "0":
    list10.append(0)

# print(list10)

ans = 0
for j in range(0, len(list10), 2):
    h = j
    t = min(N - 1, j + 2 * K)
    # print(sum(list10[j:t + 1]), j)
    ans = max(ans, sum(list10[j:t + 1]))
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
S = input()

# 1の個数, 0の個数, 1の個数, ..., 1の個数
list10 = []
head = S[0]
cnt = 0

# 左端の1の数
if S[0] == "0":
    list10.append(0)

for i in range(N):
    if S[i] == head:
        cnt += 1
    else:
        list10.append(cnt)
        cnt = 1
        head = S[i]

    if i == N - 1:
        list10.append(cnt)

# 右端の1の数
if S[-1] == "0":
    list10.append(0)

# print(list10)

ans = 0

cumsum = [0]
for li in list10:
    cumsum.append(cumsum[-1] + li)
# print(cumsum)

for j in range(1, len(cumsum), 2):
    h = j
    t = min(j + 2 * K, len(cumsum) - 1)
    ans = max(ans, cumsum[t] - cumsum[max(h - 1, 0)])
print(ans)
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
dp=[[0]*401 for _ in range(401)]
for _ in range(n):
  a,b,c=map(int,input().split())
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if i-a<0 or j-b<0:
        continue
      else:
        if dp[i-a][j-b]==0:
          continue
        else:
          if dp[i][j]==0:
            dp[i][j]=dp[i-a][j-b]+c
          else:
            dp[i][j]=min(dp[i][j],dp[i-a][j-b]+c)
  if dp[a][b]==0:
    dp[a][b]=c
  else:
    dp[a][b]=min(dp[a][b],c)
ans=10**10
for i in range(401):
  if i*ma>400 or i*mb>400:
    break
  if dp[i*ma][i*mb]==0:
    continue
  else:
    ans=min(ans,dp[i*ma][i*mb])
if ans==10**10:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
dp=[[0]*401 for _ in range(401)]
for _ in range(n):
  a,b,c=map(int,input().split())
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if i-a<0 or j-b<0:
        continue
      else:
        if dp[i-a][j-b]==0:
          continue
        else:
          if dp[i][j]==0:
            dp[i][j]=dp[i-a][j-b]+c
          else:
            dp[i][j]=min(dp[i][j],dp[i-a][j-b]+c)
  if dp[a][b]==0:
    dp[a][b]=c
  else:
    dp[a][b]=min(dp[a][b],c)
ans=10**10
for i in range(401):
  if i*ma>400 or i*mb>400:
    break
  if dp[i*ma][i*mb]==0:
    continue
  else:
    ans=min(ans,dp[i*ma][i*mb])
if ans==10**10:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

# C - Attack Survival
N, K, Q = map(int, input().split())
a = [int(input()) for i in range(Q)]
for i in range(N):
    if K-Q+(a.count(i+1)) > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

# C - Attack Survival
from collections import Counter

N, K, Q = map(int, input().split())
a = [int(input()) for i in range(Q)]
A = Counter(a)
B = 1 - (K-Q)

for i in range(N):
    if A[i+1] >= B:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ruiseki = [1]
    ruiseki2 = []
    for i in range(1, n+1):
        ruiseki.append(a[i-1]*ruiseki[i-1])
    for i in range(k-1, n):
        ruiseki2.append(ruiseki[i+1]//ruiseki[i-k+1])
    for i in range(n-k):
        if ruiseki2[i] < ruiseki2[i+1]:
            print("Yes")
        else:
            print("No")
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(k, n):
        if a[i] > a[i-k]:
            print("Yes")
        else:
            print("No")
    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

from collections import Counter

class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = {2 : n_twoes}
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res[p] = res.get(p, 0) + 1
            n //= p
        return res.values()

def f(K):
    res = 1
    for i in K:
        res *= i + 1
    return res

P = Osa_k(10**7)
print(sum(i * f(P(i)) for i in range(1, int(input()) + 1)))


### FIXED CODE ###

n = int(input())
print(sum(n//i * (i + n//i*i)//2 for i in range(1, n + 1)))
### BUGGY CODE ###

import sys

n=int(input())

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

for i in range(len(a)-1):
  for j in range(i+1,len(a)):

    if a[i]==a[j]:
      print("NO")
      sys.exit()

print("YES")

### FIXED CODE ###

import sys

n=int(input())

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

a.sort()

for i in range(len(a)-1):
  if a[i]==a[i+1]:
    print("NO")
    sys.exit()

print("YES")
### BUGGY CODE ###

from operator import mul
from functools import reduce

border = 10 ** 18

N = int(input())
nums = list(map(int, input().split()))
result = reduce(mul, nums)

if result > border:
    print(-1)
    exit()
print(result)

### FIXED CODE ###

border = 1000000000000000000

N = int(input())
nums = list(map(int, input().split()))
if 0 in nums:
    print(0)
    exit()

result = 1
for n in nums:
    result = result * n
    if result > border:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

n, k = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
 
b = []
for i in range(n):
    s = a[i]
    b.append(s)
    for j in range(i+1, n):
        s += a[j]
        b.append(s)
 
MAX = 40
ans = 0
for t in range(MAX, 0, -1):
    x = ans + (1 << (t-1))
    cnt = 0
    for v in b:
        if x & v == x:
            cnt += 1
    if cnt >= k:
        ans = x
 
print(ans)

### FIXED CODE ###

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

b = []
for i in range(n):
    r = 0
    for j in range(i,n):
        r += a[j]
        b.append(r)


n2 = n*(n+1)//2

res = 0
for i in range(41):
    p = res + 2**(40-i)
    
    c = 0
    for j in range(n2):
        if p == p&b[j]:
            c+=1
    
    if c >= k:
        res = p

print(res)
### BUGGY CODE ###

k = int(input())
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
b = 10
c = 9
while c <= k-1:
    B = str(b)
    for i in range(len(B)-1):
        if abs(int(B[i])-int(B[i+1])) > 1:
            b += 1
            break
    else:
        a.append(b)
        b += 1
        c += 1
print(a[k])

### FIXED CODE ###

k = int(input())
a = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for j in range(9):
    b = []
    for i in a[-1]:
        I = str(i)
        if I[-1] != '9':
            b.append(i*10 + int(I[-1])+1)
        b.append(i*10 + int(I[-1]))
        if I[-1] != '0':
            b.append(i*10 + int(I[-1])-1)
    a.append(b)
    A += b
ans = sorted(A)
print(ans[k-1])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

count = 0

for i in range((n//r)+1):
    for j in range((n//g)+1):
        rg = i * r + j * g
        rest = n - rg
        if rest < 0:
            continue
        elif rest == 0:
            count += 1
        elif rest % b == 0:
            count += 1

print(count)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

count = 0
a = n // r
t = n // g

for i in range(a+1):
    for j in range(t+1):
        rg = i * r + j * g
        rest = n - rg
        if rest < 0:
            continue
        elif rest % b == 0:
            count += 1

print(count)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
items = []
ap = items.append
a_sum =0 
b_sum = 0
for i in range(N):
    a, b, c = map(int, input().split())
    ap((a, b, c))
    a_sum += a
    b_sum += b

inf = float("inf")
dp = [[[inf for _ in range(b_sum + 11)] for _ in range(a_sum + 11)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)